1

我正在编写一个代码来找到一个非常大的数的最大素数。

欧拉计划第 3 题：600851475143 的最大素因数是多少？

我用 C 编写了它......但是数据类型 long long int 不足以容纳 value 。

现在，我已经用 Python 重写了代码。如何减少执行时间（因为它需要相当长的时间）？

def isprime(b):
    x=2
    while x<=b/2:
        if(b%x)==0:
            return 0
        x+=1
    return 1
def lpf(a):
    x=2
    i=2
    while i<=a/2:
        if a%i==0:
            if isprime(i)==1:
                if i>x:
                    x=i
                    print(x)
        i+=1
    print("final answer"+x)
z=600851475143
lpf(z)
4

4 回答 4

3

有许多可能的算法加速。一些基本的可能是：

  • 首先，如果您只对最大的素因子感兴趣，您应该从可能的最大因子中检查它们，而不是最小的。因此，不要循环 from 2toa/2尝试检查from a downto 2。
  • 您可以加载素数数据库而不是使用isprime函数（网络中有几十个这样的文件）
  • 此外，只有奇数可以是素数（除了2），因此您可以在每次迭代中“跳跃”2 个值

你的isprime检查器也可以加速，你不必寻找除数到b/2，检查到 就足够了，这降低了到 的sqrt(b)复杂性（假设模运算是常数时间）。O(n)O(sqrt(n))

于 2013-08-29T19:47:05.107 回答
2

您可以使用 GCC 提供的 128 int：http: //gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html。这样，您可以继续使用 C 并避免优化 Python 的速度。此外，您始终可以添加自己的自定义存储类型来保存大于 C 中 long long 的数字。

于 2013-08-29T19:45:14.703 回答
1

我认为您检查的数字太多（在每种情况下以 1 递增并从 2 开始）。如果你想通过试除法检查 is_prime，你需要除以更少的数字：只有奇数才能开始（更好的是，只有素数）。您可以通过以下方式在 python 中对奇数进行范围：

for x in range(3, some_limit, 2):
    if some_number % x == 0:
      etc.

此外，一旦你有一个素数列表，你应该能够向后遍历该列表（因为问题要求最高素数因子）并测试这些素数中的任何一个是否均分到数字中。

最后，人们在检查试除法时通常会取一个数字的平方根，因为任何超过平方根的东西都不会提供新的信息。考虑 100：

1 x 100
2 x 50
5 x 20
10 x 10
20 x 5
etc.

您只需检查数字的平方根即可找到所有重要的除数信息。这个技巧对于测试素数和测试从哪里开始寻找这个巨大数字的潜在除数都很有用。

于 2013-08-29T19:47:34.860 回答
0

首先，你的两个 while 循环只需要上升到 sqrt(n)，因为你会在更早的时候遇到任何事情（然后你还需要检查 a/i 的素数）。此外，如果你找到除它的最小数，并且除法的结果是素数，那么你找到了最大的数。

首先，更正您的isprime功能：

def isprime(b):
    x=2
    sqrtb = sqrt(b)
    while x<=sqrtb:
        if(b%x)==0:
            return 0
        x+=1
    return 1

然后，你的 lpf：

def lpf(a):
    x=2
    i=2
    sqrta = sqrt(a)
    while i<=sqrt(a):
        if a%i==0:
            b = a//i # integer
            if isprime(b):
                return b
            if isprime(i):
                x=i
                print(x)
        i+=1
    return x
于 2013-08-29T19:54:33.537 回答