0

我试图找到一个数字的最大素数。当与较小的数字一起使用时，该代码在 IDLE 上正确运行，但当我将较大的数字（如 600851475143）分配给 n 时，似乎根本不会在屏幕上打印任何内容。为什么？

def isPrime(n):
    isPrime = True
    for i in range(2,n-1):
        if n % i == 0:
            isPrime =  False
        return isPrime

largest = 0
n = 600851475143
for i in range(2,n-1):
    if isPrime(i) and n % i == 0:
        largest = i
        n = n / i
        continue

print("The largest prime factor is", largest)

顺便说一句，我正在运行 Python 3.3。

==================================================== ==============================

感谢大家！

我将我的原始代码固定如下：

def isPrime(n):
    for i in range(2,n-1):
        if n % i == 0:
            return False
    return True

largest = 0
n = 600851475143
for i in range(2,n-1):
    if isPrime(i) and n % i == 0:
        largest = i
        if i == n:
            break
        n = n / i

print("The largest prime factor is", largest)

就像nakedfanatic 说的，他们的代码运行得更快，我稍微编辑了一下：

largest = 0
n = 600851475143
i = 2
while True:
    if n % i == 0:
        largest = i
        if n == i:
            # finished
            break
        n = n / i
    else:
        i += 1

print("The largest prime factor is", largest)
4

7 回答 7

2

有几个优化领域：

  • 所有分解只需要起床sqrt(n)（包括）

  • 转换isPrime()为表查找

    使用 初始化查找表n，然后只计算一次所有素数< sqrt(n)并循环遍历它们。
    正如评论所指出的，这会占用大量内存空间。我们可以使用位标志将内存需求减少到 1/8，如果我们跳过所有偶数，我们可以再减少一半（然后必须单独测试 n 是否为偶数）。但这对于 LARGE 来说可能仍然令人生畏n。

  • （如果使用当前代码）尽早返回isPrime()（@justhalf）

  • sqrt(n)查找最大因子时向后循环（从到 2）

  • 如果除以一个因子（@justhalf）后商为 1，则提前返回

  • 这篇文章（由@prashant 建议）包含更复杂的算法（使我的建议非常幼稚><）：

    列出 N 以下所有素数的最快方法

  • ...（欢迎编辑）

于 2013-09-25T04:05:30.050 回答
1

更困难的问题可能需要不同的算法。

检查这个问题：列出N以下所有素数的最快方法

您的代码看起来不错，但大型n. 利用数学可以使您以数量级的速度更快地解决这个问题。

在该链接上，我建议rwh_primes1使用纯 python 解决方案，并且primesfrom3to作为使用 numpy 的解决方案。这两个实现都相当短，相对清晰，并且做的事情基本相同。这些代码片段是用 Python 2 编写的，因此翻译可能如下所示：

def rwh_primes1(n):
    sieve = [True] * (n//2)
    for i in range(3, int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
    return [2] + [2*i+1 for i in range(1,n//2) if sieve[i]]
于 2013-09-25T04:24:53.563 回答
1

这是因为即使n已经是 1，你也会继续尝试。

此代码将帮助您查看问题：

def isPrime(n):
    for i in xrange(2,n-1):
        if n % i == 0:
            return False
    return True

largest = 0
n = 600851475143
for i in xrange(2,n-1):
    print 'Checking whether %d divides %d' % (i,n)
    if isPrime(i) and n % i == 0:
        largest = i
        n = n / i
        continue

print("The largest prime factor is", largest)

这将产生：

...
检查 6857 是否除以 6857
检查6858是否除1
检查6859是否除1
检查6860是否除1
检查6861是否除1
检查6862是否除1
检查6863是否除1
检查6864是否除1
检查6865是否除1
检查6866是否除1
检查6867是否除1
检查6868是否除1
检查6869是否除1
检查6870是否除1
检查6871是否除1
检查6872是否除1
检查6873是否除1
...

你应该在变为1时打破循环n，这样它就不会做不必要的检查

n = n / i
if n==1:
    break
continue

而且无论如何，您的代码可能会改进很多，哈哈，请参阅其他人的建议。

于 2013-09-25T04:08:02.083 回答
1

最有可能的是，您的代码没有以 large 终止n，仅仅是因为运行循环需要很长时间。

于 2013-09-25T04:02:21.957 回答
1

您的代码在 O(n²) 时间内运行，这意味着随着 n 大小的增加，它会很快变得异常缓慢。这就是为什么您的算法适用于较小的值，但适用于较大的值。

这段代码在 O(n) 时间内做同样的事情，根本不做任何素数检查，并立即返回结果：

prime_factors = []
n = 600851475143
i = 2
while True:
    if n % i == 0:
        prime_factors.append(i)
        if n == i:
            # finished
            break
        n = n / i
    else:
        i += 1

print("The largest prime factor is", prime_factors[-1])
于 2013-09-25T04:20:11.050 回答
0

代码的另一个可能会减慢速度的方面是代码的后半部分

largest = 0
n = 600851475143
for i in range(2,n-1):
    if isPrime(i) and n % i == 0:
        largest = i
        n = n / i
        continue

特别是声明

if isPrime(i) and n % i == 0:

根据文档，仅在第一个条件为时才评估第二个条件True。在您的情况下，颠倒条件会更有意义，以便始终执行计算成本较低的除法，而isPrime()仅对实际因素调用更昂贵的除法

largest = 0
n = 600851475143
for i in range(2,n-1):
    if n % i == 0 and isPrime(i):
        largest = i
        n = n / i
        if n == 1: 
            break
于 2013-09-25T04:50:58.700 回答
0 
isPrime = True
for i in range(2,n-1):
    if n % i == 0:
        isPrime =  False
    return isPrime

由于无条件，此循环始终退出第一次迭代return。尝试：

for i in range(2,n-1):
    if n % i == 0:
        return False

return True

上限n-1也可以减少到sqrt(n)+1。

于 2013-09-25T04:04:13.847 回答