查找第20个、第30个以及第n个质数。（我能找到第20个但是找不到第30个？）[Python]

Question

这个问题是找到第1000个质数。我写了以下Python代码。问题在于，我可以得到第10个、第20个质数的正确答案，但之后每增加10就会偏离一个。我无法找出错误所在:(

count=1            #to keep count of prime numbers
primes=()          #tuple to hold primes
candidate=3        #variable to test for primes
while count<20:
    for x in range(2,candidate):
        if candidate%x==0:
            candidate=candidate+2
        else : pass
    primes=primes+(candidate,)            
    candidate=candidate+2
    count=count+1
print primes        
print "20th prime is ", primes[-1]

如果你有疑问，count的初始值为1是因为我不将2作为质数进行测试（我从3开始），而candidate增加2是因为只有奇数才可能是质数。我知道还有其他解决这个问题的方法，比如质数定理，但我想知道这种方法的问题在哪里。如果你有任何优化建议，请提出。

谢谢

- gsin

---

元组是不可变的，每次你都在复制元组，相反你应该将其初始化为列表（primes=[]），并使用primes.append() - 这对速度不会有太大影响... - Kimvais

嗯...好问题。可能不是最快的实现方式。我一直想构建一个高效的质数生成器，只要它有足够的内存计算所需，就可以无限运行下去。著名的筛法在这种情况下不起作用——你不想在开始之前选择一个要查看的数字上限。但是，每次检查新数字的O(n)复杂度也很糟糕。理想情况下，您希望有一个已计算出的质数列表和集合，并将其与模测试进行匹配。我还没有完全写出来......我知道Haskell语言有一个质数生成器。 - Hamish Grubijan

@SilentGhost 为什么？@Kimvais 我知道，我每次都在创建一个新的元组，但使用列表也无法解决我的问题@Ipthnc 这正是我想到的，但即使我自己也无法写下来，也许我会花更多时间来解决这个问题。然而，我的问题仍未解决 - gsin

这听起来很像一道欧拉计划的问题。 - JesperE

一般性的说明：只需将n除以小于等于n的平方根的所有数，就能判断n是否为质数（因为测试到n已足够）。 - Felix Kling

Answer 1

在test_generators.py中有一个很好的Eratosthenes筛生成器实现：

def intsfrom(i):
     while 1:
         yield i
         i += 1

def firstn(g, n):
     return [g.next() for i in range(n)]

def exclude_multiples(n, ints):
     for i in ints:
         if i % n:
             yield i    

def sieve(ints):
     prime = ints.next()
     yield prime
     not_divisible_by_prime = exclude_multiples(prime, ints)
     for p in sieve(not_divisible_by_prime):
         yield p

primes = sieve(intsfrom(2))

>>> print firstn(primes, 20)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

- jbochi

---

实际上，这段代码并不是埃拉托色尼筛法的实现，因为它计算了每个候选数除以已经发现的每个质数的余数……埃拉托色尼筛法根本不进行任何“除法”操作，只需要执行加法（按固定增量划去数字所需的全部计算）。Melissa E. O'Neill 写了一篇名为《真正的埃拉托色尼筛法》的好文章，讨论了这种朴素实现与真正的埃拉托色尼筛法之间的区别，文中使用了 Haskell 语言作为例子，但并非特定于 Haskell 或函数式编程，可以轻松地用 Python 重写。 - Michał Marczyk

继续超过评论长度限制... 在正确的SoE和这种天真的筛子之间，性能有着巨大的差异，尽管这并不能阻止天真的筛子在测试Python生成器实现的情况下非常合适。 :-) - Michał Marczyk

@Michal。非常注意到！它确实不是真正的筛子。谢谢。 - jbochi

Answer 2

你的 Python 代码需要进行很多改进，但是为了回答你的具体问题：

当你找到一个除数 (candidate % x == 0) 时，你增加了候选值，但是没有对 x 做任何处理。这可能会导致两个问题：

1. candidate 可能有一个除数，但它比任何被测试的 x 都要小——因为在下一次循环迭代中测试开始于 x 比之前的值高一，而不是从 2 开始。
2. candidate 可能有一个除数，但它比 x 的最大值还要大——因为你从 2 到 循环开始时 candidate 的值 中取出 x 的值。

- balpha

Answer 3

我认为这段代码并没有测试你想要测试的内容。看起来你是想说“对于2到我的候选数之间的每个数字，检查候选数是否可以被该数字整除”。然而，当你找到一个质数（candidate%x == 0）时，你只增加了候选数 - 你仍然需要重新开始“for x in ...”循环，因为候选数已经改变。

从代码中我能够看到这一点；当然，还有许多其他方法和优化可供使用。

- Ben Zotto

Answer 4

很好知道，大于3的每个质数都可以写成6k-1/+1。

当你在寻找下一个候选者时，你总是可以像这样编写代码（代码片段使用C语言）：

a=1;
...
candidate=6*k+(a=(a==-1)?1:-1);
if(a==1){
           k++;
}

以下是一个我不久前使用过的函数，用于确定第n个质数，其中LIM是您要查找的第n个数字（C代码）：

int sol2(){
        int res,cnt,i,k,a;
        res=-1;
        i=1;
        cnt=3;
        k=1;
        a=1;
        while (1){
                if (util_isprime(cnt)){
                        i++;
                        if (i==LIM){
                                res=cnt;
                                break;
                        }
                }
                /* 6k+/-1 starting from 6*1-1 */
                cnt=6*k+(a=(a==-1)?1:-1);
                if(a==1){
                        k++;
                }
        }
        return res;
}

- Andrei Ciobanu

Answer 5

在这个语句中：

for x in range(2,candidate)

您可以通过扫描sqrt（candidate）来减少迭代次数。

如果候选数可被x整除，则我们可以写成candidate = x * b，其中b是某个数。如果x小于或等于b，则x必须小于或等于候选数的平方根。

- Pierre

Answer 6

如果你想要任何有效的东西，就使用埃拉托斯特尼筛法 - 它既简单又古老。

MAX = 10000
candidates = [True] * MAX
candidates[0] = False
candidates[1] = False

primelist = []
for p,isprime in enumerate(candidates):
    if isprime:
        primelist.append(p)
        for n in range(2*p,MAX,p):
            candidates[n] = False

print primelist[1001]

- Jochen Ritzel

---

我看到了这个，但如果我想要前20,000个质数呢？那么很难选择MAX。另外，如果我想无限制地继续下去呢？ - Hamish Grubijan

在 x 以下大约有 x/log x 个质数，因此您可以直接计算MAX。还有其他算法可以找到非常大的质数。 - Jochen Ritzel

Answer 7

顺便说一下...我用以下代码解决了这个问题，虽然它可以进行更多的优化，但我首先想以这种方式解决它。感谢大家的帮助。

from math import *
primes=[2,3]
count=2
testnumber=5
while count<1000:

    flag=0
    for x in range(2,testnumber):
        if x<=sqrt(testnumber):
            if testnumber%x==0:
                #print testnumber , "is not a prime"
                flag=1

            else : pass
    if flag!=1:
        #print testnumber , "is a prime"
        primes=primes+[testnumber]
        count=count+1
    testnumber=testnumber+2


#print primes
print "1000th prime is ", primes[-1]

我现在会看一下你们提到的所有其他算法

- gsin

Answer 8

C初学者

#include<stdio.h>
int main ()

{
int a,s,c,v,f,p,z;

while(scanf("%d",&f) !=EOF){
p=0;
for(z=1;p<f;z++){
                s=2;
                a=z;
                while(s<a){
                          if(a%s==0)s=a+1;
                          else s=s+1;
                          }
                if (s!=a+1)p++;

                }
printf("%d\n",a);
                            }

return 0;
}

- Saikot

Answer 9

关于优化，如果您确定要遵循此实现，可以避免查看以下数字：

1. 以5结尾，因为它们可被5整除。
2. 由相同数字组成，例如22、33、44、55、66等，因为它们可被11整除。

但不要忘记将5和11添加为质数！

- Alex Ntousias

---

如果除数可以是之前收集的质数列表，那将会很容易。我想我会采用这种方法。现在就把它写成代码！ - gsin

@Alex：假设OP使用的是二进制计算机，检查最后一位10进制数字是否为5与一开始就除以5是相同的。你第二点的论点也类似。 - balpha

#2在二进制计算机上并不是真正的优化。#1可以推广实现一些叫做“筛法”的东西。你拿前k个质数，比如2、3、5，然后只尝试那些不能被这些质数整除的候选数。因此，对于模30，这意味着您只尝试具有以下余数模235的候选数：[1、7、11、13、17、19、23、29]。因此，您可以像这样编写代码： primes=[2,3,5]; for base in xrange(0, 10000000, 235): for rem_mod30 in [1, 7, 11, 13, 17, 19, 23, 29]: candidate = base + rem_mod30 # 检查候选数是否为质数 - President James K. Polk

Answer 10

除非我大错特错，您总是将当前候选数添加到质数列表中，无论是否已找到除数。您用于附加到质数列表的代码（撇开早先提到的不可变元组注释）在整数除数测试之外，因此始终运行。

- tw39124