巨大数的最大素因数失败
Largest prime factor on huge number failed
我正在研究 Euler Project 问题,这是问题五:
最大质因数
问题3
13195的质因数是5,7,13,29.
数 600851475143 的最大质因数是多少?
我得到了工作代码:
def factor(x, f=2):
while x >= f*f:
while x % f == 0:
x = int(x/f)
factor = f
f += 1
print(f'x = {x},\nlast factor = {factor}') # print for debug only
return max(x, factor)
因子(19*19*19*19*19*19*19*19*19*1999989899)
x = 33170854034208712,
最后一个因素 = 182128674
33170854034208712
有谁知道为什么这不能产生正确的答案?
我只是从头开始推理这个问题。下面是我的代码,看起来很像你的
def largest_prime_divisor(x, f=2):
while f**2 <= x:
if x % f == 0:
x //= f
else:
f+=1
return x
print(largest_prime_divisor(25)) # 5
print(largest_prime_divisor(13195)) # 29
n = 19*19*19*19*19*19*19*19*19*1999989899
print(largest_prime_divisor(n)) # 577 this is prime
您应该使用整数除法运算符 // 而不是浮点数除法运算符 /
除此之外你的代码是正确的
while x % f == 0:
x = int(x//f)
factor = f
输出
x = 577,
last factor = 541
除法运算符区别
Python 3.7.1 (default, Nov 6 2018, 18:46:03)
[Clang 10.0.0 (clang-1000.11.45.5)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>>
>>>
>>> print(645372136089564734321//19)
33966954531029722859
>>> print(645372136089564734321/19)
3.396695453102972e+19
我正在研究 Euler Project 问题,这是问题五:
最大质因数 问题3 13195的质因数是5,7,13,29.
数 600851475143 的最大质因数是多少?
我得到了工作代码:
def factor(x, f=2):
while x >= f*f:
while x % f == 0:
x = int(x/f)
factor = f
f += 1
print(f'x = {x},\nlast factor = {factor}') # print for debug only
return max(x, factor)
因子(19*19*19*19*19*19*19*19*19*1999989899)
x = 33170854034208712, 最后一个因素 = 182128674
33170854034208712
有谁知道为什么这不能产生正确的答案?
我只是从头开始推理这个问题。下面是我的代码,看起来很像你的
def largest_prime_divisor(x, f=2):
while f**2 <= x:
if x % f == 0:
x //= f
else:
f+=1
return x
print(largest_prime_divisor(25)) # 5
print(largest_prime_divisor(13195)) # 29
n = 19*19*19*19*19*19*19*19*19*1999989899
print(largest_prime_divisor(n)) # 577 this is prime
您应该使用整数除法运算符 // 而不是浮点数除法运算符 /
除此之外你的代码是正确的
while x % f == 0:
x = int(x//f)
factor = f
输出
x = 577,
last factor = 541
除法运算符区别
Python 3.7.1 (default, Nov 6 2018, 18:46:03)
[Clang 10.0.0 (clang-1000.11.45.5)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>>
>>>
>>> print(645372136089564734321//19)
33966954531029722859
>>> print(645372136089564734321/19)
3.396695453102972e+19