Программа факторизации Pascal / Python

Question

Я создал две программы, чтобы найти основные множители числа, одну на python и одну на паскале.Я хотел бы факторизовать 600851475143;программа python мгновенно ее разлагает.Тем не менее, паскаль не заканчивается в разумные сроки.Это связано с другим языком программирования или с тем, как я кодировал язык на Паскале?Я использовал рекурсию в питоне, но не в паскале.Почему программа на паскале также не завершается мгновенно?

python:

def findLowestFactor(num, factors=None):
    if factors:
        start = factors[-1]
    else:
        start = 2
    for i in range(start, int(num)):
        if num%i == 0:
            return i
    else:
        return False


def findPrimeFactors(num, factors=None):
    if factors is None:
        factors = []
    factor = findLowestFactor(num, factors)
    if factor:
        factors.append(factor)
        findPrimeFactors(num/factor, factors)
        return factors
    else: 
        factors.append(int(num))
        return factors


if __name__ == "__main__":
    while True:
        num = int(input("Please enter a number: "))
        factors = findPrimeFactors(num)
        print(*factors)

Pascal:

program Primes;

var
  input:string;
  num:integer;
  error:integer;
  factor:integer;
  factors:array of integer;
  found: boolean;
  start:integer;
  x:integer;


begin
  writeln(600851475143);
  (*Repeat untill exit*)
  while true do
  begin
    (*Repeat untill valid input*)
    repeat
    write('Enter a number: ');
    readln(input);
    val(input, num, error);
    if error = 1 then
      writeln('Not an integer');
    until error = 0;

    writeln;

    (*set up list*)
    SetLength(factors, 0);
    factor := 0;
    found := false;
    (*while num is not prime*)
    while found = false do
    begin
      (*start from largest factor found for efficiency*)
      if length(factors) > 0 then
        start := factors[length(factors)-1]
      else
        start := 2;
      (*loop through numbers from number in start var to current num*)
      for factor := start to num do
      begin
        (*if there are no more factors*)
        if num / factor = 1 then
          begin;
            (*add final factor to list*)
            SetLength(factors, length(factors)+1);
            factors[length(factors)-1] := factor;
            (*break out of the loop*)
            found := True;
          end
        (*if factor is found*)
        else if num mod factor = 0 then
          begin
            (*divide num by found factor*)
            num := num div factor;
            (*add the factor*)
            SetLength(factors, length(factors)+1);
            factors[length(factors)-1] := factor;
            (*break for efficiency*)
            Break;
          end;


      end;
    end;

    write('Prime Factors: ');
    for x:= 0 to length(factors)-1 do
      write(factors[x], ' ');
    writeln;
    writeln;

  end;

end. 

Answer 1

Я перевел ваш код Python на Паскаль.Я использовал Delphi, но он должен компилироваться и во FreePascal.Возвращается мгновенно:

type
  TIntArray = array of Integer; // Delphi: TArray<Integer>;

function findLowestFactor(num: Int64; factors: TIntArray): Integer;
var
  start: Integer;
  i: Int64;
begin
  if Length(factors) > 0 then
    start := factors[High(factors)]  // factors[-1] in Python, i.e. last entry.
  else
    start := 2;
  i := start;
  while i < num do        // Int64 can not be used as index in for-loop... 
  begin                   // ... so I use while loop.
    if num mod i = 0 then // Python: if num % i == 0:
      Exit(i);            // return i
    Inc(i);
  end;
  Exit(0);
end;

procedure findPrimeFactors(num: Int64; var factors: TIntArray);
var
  factor: Integer;
begin
  factor := findLowestFactor(num, factors);
  if factor > 0 then
  begin 
    // Delphi: factors := factors + [factor];
    SetLength(factors, Length(factors) + 1);
    factors[High(factors)] := factor;

    findPrimeFactors(num div factor, factors);
  end
  else
  begin
    // Delphi: factors := factors + [Integer(num)];
    SetLength(factors, Length(factors) + 1);
    factors[High(factors)] := Integer(num);
  end;
end;

const
  testValue: Int64 = 600851475143;

var
  factors: TIntArray;
  i: Integer;
  result: Int64;

begin
  // Instead of user input, I use the testValue above.
  Writeln('test value: ', testValue);
  findPrimeFactors(testValue, factors);
  result := 1;
  for i in factors do
  begin
    Write(i:8);
    result := result * i;
  end;
  Writeln;
  Writeln('multiplied: ', result);
  Readln;
end.

Обратите внимание, что мне приходилось использовать Int64 в некоторых местах .Я предполагаю, что Python делает это автоматически, но не Pascal.Возможно, использование целых чисел в некоторых местах делало ваш код таким медленным.

Я пропустил части кода, вводимые пользователем (Readln и т. Д.), Просто использовал заданное вами постоянное значение.Но, как я уже сказал, он возвращается мгновенно с правильными значениями (см. Переменный результат).