Pascal/Python 分解程序
Pascal/Python Factorization Program
我编写了两个程序来求一个数的质因数,一个是 python,一个是 Pascal。我想分解 600851475143; python 程序立即将其分解。然而,pascal 并没有在合理的时间内完成。这与不同的编程语言有关,还是我如何用 Pascal 编写代码?我在 python 中使用了递归,但在 Pascal 中没有使用。为什么 pascal 程序没有立即完成?
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)
帕斯卡:
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.
我已将您的 Python 代码翻译成 Pascal。我使用 Delphi,但它也应该在 FreePascal 中编译。它returns瞬间:
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 等),只是使用了您提供的常量值。但是,正如我所说,它立即 returns,具有正确的值(参见变量结果)。
我编写了两个程序来求一个数的质因数,一个是 python,一个是 Pascal。我想分解 600851475143; python 程序立即将其分解。然而,pascal 并没有在合理的时间内完成。这与不同的编程语言有关,还是我如何用 Pascal 编写代码?我在 python 中使用了递归,但在 Pascal 中没有使用。为什么 pascal 程序没有立即完成?
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)
帕斯卡:
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.
我已将您的 Python 代码翻译成 Pascal。我使用 Delphi,但它也应该在 FreePascal 中编译。它returns瞬间:
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 等),只是使用了您提供的常量值。但是,正如我所说,它立即 returns,具有正确的值(参见变量结果)。