总理分解：不适用于大数？

Question

我正在尝试查找数字的最大素数因子。当使用较小的数字时，代码在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) 

Answer 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) 

这将产生：

 
... 
Checking whether 6857 divides 6857 
Checking whether 6858 divides 1 
Checking whether 6859 divides 1 
Checking whether 6860 divides 1 
Checking whether 6861 divides 1 
Checking whether 6862 divides 1 
Checking whether 6863 divides 1 
Checking whether 6864 divides 1 
Checking whether 6865 divides 1 
Checking whether 6866 divides 1 
Checking whether 6867 divides 1 
Checking whether 6868 divides 1 
Checking whether 6869 divides 1 
Checking whether 6870 divides 1 
Checking whether 6871 divides 1 
Checking whether 6872 divides 1 
Checking whether 6873 divides 1 
... 

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

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

不管怎样，你的代码可能会被很多可以改善，哈哈，看到别人的建议。

Answer 2

最有可能的，你的代码是不是结束与大n，只是因为它需要很长时间才能通过循环。

Answer 3

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。

Answer 4

有优化的几个方面：

• 全部分解只需要起身sqrt(n)（含）

• 转换isPrime()以表查找

  使用初始化一个查找表n，那么你只计算一次素数< sqrt(n)并遍历它们。
  正如评论指出的，这占用了大量的内存空间。我们可以使用位标志来将内存要求降低到1/8，如果我们跳过所有的偶数（然后必须测试n是否分开），我们可以将其减半。但是，对于大型n来说，这仍然是艰巨的。

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

• 环向后（从sqrt(n) 2）早期仰视当最大因素

• 回报如果商数除以一个因子后为1（by @justhalf）

• 这篇文章（由@prashant建议）包含更复杂的算法THM（使我的建议很天真> <）：

  Fastest way to list all primes below N

• ...（编辑欢迎）

Answer 5

您的代码在O（n2）时间内运行，这意味着随着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]) 

Answer 6

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

检查这个问题了：Fastest way to list all primes below 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]] 

Answer 7

你的代码可以减缓下来的另一个方面是

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: 

每documentation，如果第一个是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