我在研究Euler项目的问题,这是问题五:
最大素因子问题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
我试图解决这个问题:https://www.hackerrank.com/contests/projecteuler/challenges/euler003/submissions/code/2977447 13195的质因数是5、7、13、29。 给定数N的最大素因子是什么? 输入格式第一行包含T,测试用例数。后面是T行,每行包含一个整数N。 每个测试用例的输出格式,显示N的最大素因子。 约束条
这就是Euler项目的问题3。对于那些不知道的人,我必须找出最大的素因子600851475143。我有以下代码: 但是,当我用比600851475143小(很多)的东西测试程序时,比如100000000,那么程序需要时间——事实上,100000000到目前为止已经花了20分钟,而且还在继续。很明显,我在这里的做法是错误的(是的,这个程序确实有效,我用较小的数字进行了尝试)。有人能提出一种不那么详尽
我试图解决欧拉项目问题3,即: 13195的主要因子为5、7、13和29。数字600851475143中最大的素因子是什么? 这是我的解决方案,它适用于较小的值,但对于所需的数字却无法完成:
O(n^2)算法简单。有没有人对此有更好的算法?
在一本书(算法导论,但我不记得是哪一章)中,我学到了求解两元素间最大差值问题: 两个元素之间的最大差,使得较大的元素出现在较小的数之后。 查找数组(至少包含一个数字)中和最大的相邻子数组。 例如,给定数组[-2,1,-3,4,-1,2,1,-5,4],相邻子数组[4,-1,2,1]的最大和=6。 为了解决的两元素间最大差异问题,可以将其转化为数组的最大子数组问题: 我在想为什么。