6

問題は、1000 番目の素数を見つけることです。このために、次の python コードを作成しました。問題は、10 番目と 20 番目の素数について正しい答えが得られることですが、その後は 10 ずつインクリメントするたびに 1 つずれてしまいます。ここでバグをキャッチできません:(

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]

ご参考までに、素数として 2 をテストしていないため (私は 3 から始めています)、count は 1 として初期化され、candidate奇数のみが素数になる可能性があるため 2 ずつインクリメントされます。素数定理など、この問題を解決する他の方法があることは知っていますが、このアプローチの何が問題なのか知りたいです。また、考えている最適化があれば、提案してください。

ありがとうございました

4

10 に答える 10

8

test_generators.pyには、素敵なエラトステネスのふるいジェネレーターの実装があります。

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。これにより、次の 2 つの問題が発生する可能性があります。

  1. candidate除数があるかもしれませんが、xテストされるものよりも小さいです。これは、ループの次の反復でのテストが、以前xの値よりも 1 大きい値で開始されるためです。xではありません2。
  2. candidate除数があるかもしれませんが、ループを開始したときの値から の値を取得するため、これまでよりも大きくなります。xx2candidate
于 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) までスキャンすることで反復回数を減らすことができます

候補が x で割り切れる場合、b に対して候補 = x*b と書くことができます。x が b 以下の場合、x は候補の平方根以下でなければなりません。

于 2010-01-03T19:38:09.733 に答える
0

最適化に関しては、この実装に従うことが確実である場合は、次のような数値を見ないようにすることができます。

  1. それらは5で割り切れるので、5で終わります。
  2. 11で割り切れるため、22、33、44、55、66などの同じ数字で構成されます。

ただし、素数として5と11を追加することを忘れないでください！

于 2010-01-03T19:22:43.457 に答える
0

私が非常に間違っていない限り、除数が見つかったかどうかに関係なく、常に現在の候補を素数のリストに追加しています。素数のリストに追加するコード（前に作成した不変のタプルコメントは別として）は、整数除数のテストの範囲外であるため、常に実行されます。

于 2010-01-03T19:26:02.427 に答える
0

リモートで効率的なものが必要な場合は、エラトステネスのふるいを実行してください。古いものと同じくらい簡単です。

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

参考までに...次のコードで解決しましたが、はるかに最適化できますが、最初にこの方法で解決したかっただけです。助けてくれてありがとう。

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

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;
}
于 2010-05-25T12:41:47.617 に答える