python - Pythonで1000番目の素数を生成するには?

Question

count = 0
i = 11

while count <= 1000 and i <= 10000:
    if i%2 != 0:
       if (i%3 == 0 or i%4 == 0 or i%5 == 0 or i%6 == 0 or i%7 == 0 or i%9 == 0):
           continue
       else:
           print i,'is prime.'
           count += 1
    i+=1

ループのみを使用して、1000 番目の素数を生成しようとしています。素数を正しく生成しますが、取得した最後の素数は 1000 番目の素数ではありません。そのためにコードを変更するにはどうすればよいですか。助けてくれてありがとう。

編集:私は今、この問題を解決する方法を理解しています. しかし、誰かが次のコードが機能しない理由を説明できますか? これは、ここに 2 番目のコードを投稿する前に書いたコードです。

count = 1
i = 3
while count != 1000:
    if i%2 != 0:
       for k in range(2,i):
          if i%k == 0:
            print(i)
            count += 1
            break
     i += 1

score 9 · Accepted Answer

どれどれ。

count = 1
i = 3
while count != 1000:
    if i%2 != 0:
       for k in range(2,i):
          if i%k == 0:        # 'i' is _not_ a prime!
            print(i)       # ??
            count += 1     # ??
            break
     i += 1          # should be one space to the left,
                     # for proper indentation

の場合i%k==0、iは素数ではありません。素数ではないことを検出した場合は、(a) 印刷しない、(b)見つかった素数のカウンターをインクリメントしないfor、(c) 実際にループから抜け出す必要があります。これ以上数値をテストする必要はありません。

また、をテストする代わりに、から始めてi%2だけインクリメントすることもできます。23

だから、私たちは今持っています

count = 1
i = 3
while count != 1000:
    for k in range(2,i):
        if i%k == 0:       
            break
    else:
        print(i)
        count += 1
    i += 2

ループが途中で抜け出さなかった場合、elseafterforが実行されます。for

動作しますが、あまりにもハードに動作するため、必要以上に遅くなります。それより下のすべての数値で数値をテストしますが、平方根までテストするだけで十分です。なんで？との間の数値n == p*qがの場合、またはの少なくとも 1 つがの平方根よりも大きくないため、両方が大きければ、それらの積はよりも大きくなります。pq1npqnn

したがって、改善されたコードは次のとおりです。

from math import sqrt

count = 1
i = 1
while count < 1000:
    i += 2
    for k in range(2, 1+int(sqrt(i+1))):
        if i%k == 0:       
            break
    else:
        # print(i) ,
        count += 1
        # if count%20==0: print ""
print i

（前のコードのように）で実行してみてrange(2,i)、どれだけ遅くなるかを確認してください。素数が 1000 の場合は 1.16 秒、2000 の場合は 4.89 秒 (3000 の場合は 12.15 秒) かかります。しかし、を使用するsqrtと、3000 個の素数を生成するのに 0.21 秒しかかからず、10,000 個の素数の生成に 0.84 秒、20,000 個の素数の生成に 2.44 秒かかります (対の増加の順序)。~ n^2.1...2.2~ n^1.5

上記で使用したアルゴリズムは、試行分割として知られています。最適な試行区分にするために必要なもう 1 つの改善があります。つまり、素数のみによるテストです。例をここで見ることができます。これは、約 3 倍速く実行され、より経験的な複雑さで実行されます。~ n^1.3

次に、Eratosthenes のふるいがあります。これは非常に高速です (20,000 素数の場合、上記の「改善されたコード」よりも 12 倍高速であり、その後はさらに高速です:素数を生成するための経験的な成長順序は、n = 1,000,000 素数まで測定されます)。):~ n^1.1n

from math import log

count = 1 ; i = 1 ; D = {}
n = 100000                        # 20k:0.20s 
m = int(n*(log(n)+log(log(n))))   # 100k:1.15s 200k:2.36s-7.8M 
while count < n:                  #            400k:5.26s-8.7M 
        i += 2                    #            800k:11.21-7.8M 
        if i not in D:            #            1mln:13.20-7.8M (n^1.1)
            count += 1
            k = i*i
            if k > m:  break      # break, when all is already marked
            while k <= m:
                D[k] = 0 
                k += 2*i
while count < n:
        i += 2
        if i not in D: count += 1
if i >= m: print "invalid: top value estimate too small",i,m ; error
print i,m

ここでテストしたように、エラトステネスの真に無制限で漸進的な「スライド」ふるいは、この範囲でさらに約 1.5 倍高速です。

score 5 · Accepted Answer

いくつかの問題が明らかです。まず、11 から開始しているため、最初の 5 つの素数は既にスキップされているため、カウントは 5 から開始する必要があります。

さらに重要なことは、プライム検出アルゴリズムが機能しないことです。この種の単純な「エラトスタネスのふるい」のような素数検出では、i より小さい素数をすべて追跡する必要があります。たとえば、アルゴリズムは 11 * 13 = 143 を素数と見なしますが、明らかにそうではありません。

ここでのPGsimple1は、ここで実行しようとしている主要な検出の正しい実装ですが、そこにある他のアルゴリズムははるかに高速です。

score 3 · Accepted Answer

素数を正しくチェックしていますか? 典型的な解決策は、機能することがわかっている別の「isPrime」関数を用意することです。

def isPrime(num):
    i = 0
    for factor in xrange(2, num):
        if num%factor == 0:
            return False
    return True

（オッズだけチェックする、平方根以下の数字だけチェックするなど、上記の機能をより効果的にする方法もあります。）

次に、n 番目の素数を見つけるには、見つかるまですべての素数を数えます。

def nthPrime(n):
    found = 0
    guess = 1
    while found < n:
        guess = guess + 1
        if isPrime(guess):
            found = found + 1
    return guess

score 2 · Accepted Answer

あなたの論理はそれほど正しくありません。その間：

if i%2 != 0:
    if (i%3 == 0 or i%4 == 0 or i%5 == 0 or i%6 == 0 or i%7 == 0 or i%9 == 0):

これでは素数かそうでないか判断できません。

sqrt(i) 以下のすべての数値が i を除算するかどうかを確認する必要があると思います。

score 1 · Accepted Answer

おそらくSOで、どこかで出会ったis_prime関数があります。

def is_prime(n):
  return all((n%j > 0) for j in xrange(2, n))

primes = []

n = 1
while len(primes) <= 1000: 
    if is_prime(n):
        primes.append(n)
    n += 1

または、すべてをループで処理したい場合は、is_prime 関数の戻り値を使用してください。

primes = []    
n = 1
while len(primes) <= 1000: 
    if all((n%j > 0) for j in xrange(2, n)):
        primes.append(n)
    n += 1

score 0 · Accepted Answer

n=2                         ## the first prime no.
prime=1                     ## we already know 2 is the first prime no.
while prime!=1000:          ## to get 1000th prime no.
    n+=1                    ## increase number by 1
    pon=1                   ## sets prime_or_not(pon) counter to 1
    for i in range(2,n):    ## i varies from 2 to n-1
        if (n%i)==0:        ## if n is divisible by i, n is not prime
            pon+=1          ## increases prime_or_not counter if  n is not prime
    if pon==1:              ## checks if n is prime or not at the end of for loop
        prime+=1            ## if n is prime, increase prime counter by 1
print n                     ## prints the thousandth prime no.

score 0 · Accepted Answer

私はちょうどこれを書いた。ユーザーが見たい素数の数を尋ねます。この場合は 1000 になります。自由に使用してください :)。

# p is the sequence number of prime series
# n is the sequence of natural numbers to be tested if prime or not
# i is the sequence of natural numbers which will be used to devide n for testing
# L is the sequence limit of prime series user wants to see
p=2;n=3
L=int(input('Enter the how many prime numbers you want to see: '))
print ('# 1  prime is 2')
while(p<=L):
    i=2
    while i<n:
        if n%i==0:break
        i+=1
    else:print('#',p,' prime is',n); p+=1
    n+=1 #Line X

#when it breaks it doesn't execute the else and goes to the line 'X'

score 0 · Accepted Answer

これを試して：

def isprime(num):
    count = num//2 + 1
    while count > 1:
        if num %count == 0:
            return False
        count -= 1
    else:
        return True

num = 0
count = 0
while count < 1000:
    num += 1
    if isprime(num):
        count += 1
    if count == 1000:
        prime = num

コードの問題:

i <= 10000 かどうかを確認する必要はありません。
あなたはこれをやっています
```
if i%2 != 0:
    if (i%3 == 0 or i%4 == 0 or i%5 == 0 or i%6 == 0 or i%7 == 0 or i%9 == 0):
```
ここでは、数値が 7 より大きい素数で割り切れるかどうかをチェックしていません。したがって、結果は、ほとんどの場合 11 で割り切れます。
2.あなたのアルゴリズムは、17 * 13 * 11が素数であると言います(そうではありません)

score 0 · Accepted Answer

これはどう：

#!/usr/bin/python

from math import sqrt

def is_prime(n):
    if n == 2:
        return True
    if (n < 2) or (n % 2 == 0):
        return False
    return all(n % i for i in xrange(3, int(sqrt(n)) + 1, 2))

def which_prime(N):
    n = 2
    p = 1
    while True:
        x = is_prime(n)
        if x:
            if p == N:
                return n
            else:
                p += 1
        n += 1
print which_prime(1000)

score 0 · Accepted Answer

if & while ループのみを使用する方法を次に示します。これにより、1000 番目の素数のみが出力されます。2 をスキップします。これは、MIT の OCW 6.00 コースの問題セット 1 として作成したため、2 回目の講義までに教えられたコマンドのみが含まれています。

prime_counter = 0  
number = 3  

while(prime_counter < 999):
    divisor = 2
    divcounter = 0
    while(divisor < number):
        if(number%divisor == 0):
            divcounter = 1  
        divisor += 1
    if(divcounter == 0):
        prime_counter+=1
    if(prime_counter == 999):
        print '1000th prime number: ', number
    number+=2

score 0 · Accepted Answer

ここにさらに別の提出物があります：

ans = 0;
primeCounter = 0;
while primeCounter < 1000:
    ans += 1;    
    if ans % 2 != 0: 
        # we have an odd number
        # start testing for prime
        divisor = 2;
        isPrime = True;
        while divisor < ans:
            if ans % divisor == 0: 
                isPrime = False;
                break;
            divisor += 1;
        if isPrime:             
            print str(ans) + ' is the ' + str(primeCounter) + ' prime';
            primeCounter += 1;
print 'the 1000th prime is ' + str(ans);

score 0 · Accepted Answer

これはおそらくより高速です: range(2,num) の代わりに num を 2 から sqrt(num)+1 に分割してみてください。

from math import sqrt

i = 2 
count = 1

while True:
    i += 1
    prime = True
    div = 2
    limit = sqrt(i) + 1
    while div < limit:
        if not (i % div):
            prime = False
            break
        else:
            div += 1
    if prime:
        count += 1
    if count == 1000:
        print "The 1000th prime number is %s" %i
        break

python - Pythonで1000番目の素数を生成するには?

13 に答える 13

Related

Reference