Project Euler 的问题在于,通常有一种明显的蛮力方法来解决问题,这将花费几乎永远的时间。随着问题变得越来越困难,您将需要实施巧妙的解决方案。
解决这个问题的一种方法是使用一个循环,它总是找到一个数字的最小(正整数)因子。当一个数的最小因数是那个数时,你就找到了最大的质因数!
详细算法说明:
您可以通过保留三个变量来做到这一点:
您要考虑的数字 (A) 当前除数存储 (B) 最大除数存储 (C)
最初,让 (A) 成为您感兴趣的数字 - 在这种情况下,它是 600851475143。然后让 (B) 成为 2。有一个条件来检查 (A) 是否可以被 (B) 整除。如果它可整除,则将 (A) 除以 (B),将 (B) 重置为 2,然后返回检查 (A) 是否可被 (B) 整除。否则,如果 (A) 不能被 (B) 整除,则将 (B) 增加 +1,然后检查 (A) 是否可被 (B) 整除。运行循环直到 (A) 为 1。返回的 (3) 将是 600851475143 的最大素数除数。
有很多方法可以使这更有效——而不是递增到下一个整数,你可以递增到下一个必须的素数整数,而不是保持最大的除数存储,你可以只返回当前数字,当它唯一的除数是本身。但是,我上面描述的算法无论如何都会在几秒钟内运行。
python中的实现如下:-
def lpf(x):
lpf = 2;
while (x > lpf):
if (x%lpf==0):
x = x/lpf
lpf = 2
else:
lpf+=1;
print("Largest Prime Factor: %d" % (lpf));
def main():
x = long(raw_input("Input long int:"))
lpf(x);
return 0;
if __name__ == '__main__':
main()
示例:让我们使用上述方法找到 105 的最大素数。
让 (A) = 105. (B) = 2(我们总是从 2 开始),我们还没有 (C) 的值。
(A) 能被 (B) 整除吗?否。将 (B) 增加 +1:(B) = 3。 (A) 可以被 (B) 整除吗?是的。(105/3 = 35)。迄今为止发现的最大除数是 3。令 (C) = 3。更新 (A) = 35。重置 (B) = 2。
现在,(A)可以被(B)整除吗?否。将 (B) 增加 +1:(B) = 3。 (A) 可以被 (B) 整除吗?否。将 (B) 增加 +1:(B) = 4。 (A) 可以被 (B) 整除吗?否。将 (B) 增加 +1:(B) = 5。 (A) 可以被 (B) 整除吗?是的。(35/5 = 7)。我们之前找到的最大除数存储在 (C) 中。(C) 当前为 3。5 大于 3,因此我们更新 (C) = 5。我们更新 (A)=7。我们重置 (B)=2。
然后我们重复 (A) 的过程,但我们将继续递增 (B) 直到 (B)=(A),因为 7 是素数并且除了它自己和 1 之外没有除数。(我们可以在 (B) 时停止)>((A)/2),因为整数除数不能大于数字的一半 - 任何数字的最小除数(除 1 之外)都是 2!)
所以此时我们返回 (A) = 7。
试着手工做一些,你就会掌握这个想法