6

问题是找到第 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，因为只有奇数可以是素数。我知道还有其他方法可以解决这个问题，例如素数定理，但我想知道这种方法有什么问题。另外，如果您有任何优化想法，请提出建议。

谢谢你

4

10 回答 10

8

在 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]

替代文字

于 2010-01-03T19:54:41.300 回答
5

您的 Python 代码有很多（！）需要改进，但要回答您的具体问题：

当你找到一个除数 ( candidate % x == 0) 时，你增加了候选者，但你不做任何事情x。这会导致两个问题：

  1. candidate可能有一个除数，但它比任何x被测试的要小——因为循环的下一次迭代中的测试从x比x之前的值高一个开始；不在2。
  2. candidate可能有一个除数，但它比以往任何时候都大x，因为您x从值 from2到启动循环时的值candidate。
于 2010-01-03T19:16:25.077 回答
3

我不认为这是在测试你认为它在测试的东西。看起来您想说“对于 2 和我的候选人之间的每个数字，检查候选人是否可以被该数字整除”。然而，当你找到一个素数 (candidate%x == 0) 时，你只是在增加候选者——你仍然需要重新开始你的“for x in ...”循环，因为候选者已经改变了。

这就是我从编写的代码中可以看到的；当然还有很多其他方法和其他优化可以在这里使用。

于 2010-01-03T19:09:00.723 回答
2

很高兴知道每个大于 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;
}
于 2010-01-03T19:31:24.723 回答
2

在声明中：

for x in range(2,candidate)

您可以通过扫描到 sqrt(candidate) 来减少迭代次数

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

于 2010-01-03T19:38:09.733 回答
0

如果您想要任何远程高效的东西，请使用Eratosthenes 筛法——它既简单又古老。

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]
于 2010-01-03T19:47:13.163 回答
0

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

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

不要忘记添加 5 和 11 作为素数！

于 2010-01-03T19:22:43.457 回答
0

除非我大错特错，否则无论是否找到除数，您总是将当前候选者添加到素数列表中。您要附加到素数列表的代码（撇开前面所做的不可变元组注释）不在整数除数测试范围内，因此始终运行。

于 2010-01-03T19:26:02.427 回答
0

仅供参考...我用下面的代码解决了它，虽然它可以优化得更多，我只是想先用这种方式解决它。感谢大家的帮助。

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]

我现在将看看你们提到的所有其他算法

于 2010-01-04T16:50:18.863 回答
0

初学者

#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;
}
于 2010-05-25T12:41:47.617 回答