0

私のジェネレーターはうまく機能します。何度もテストしました。ただ、問題があります: 数が増えると、信じられているように、プログラムは遅くなります。私はこれを行う方法を考え出しましたが、あまり前にPythonを使い始めたばかりなので、方法がわかりません。

私のジェネレーターは次のようになります。

    while 0==0:
        i=input('Enter the number for which all previous shall be tested for primality: ')
        n=0
        a=[0,1,2]
        while n<=i:
            n=n+1
            for b in range(2,n):
                if n%b==0:
                    break
                if b==(n-1):
                    a.append(n)
                    print a`

a=[0,1,2] を while 0==0 の前のスペースに移動すると、プログラムの実行中に以前の使用からのすべての数値が累積されることがわかりました。これについて変更したいのは、 が素数を蓄積するにつれて、それらを使用して次の不明な数に追いつくことです。たとえば、100 までのすべての素数が必要だったとします。次に、200 までのすべての素数が必要でした。100 までの素数を再計算する代わりに、それらをスキップしてから続行するようにプログラムしたいと思います。 100の後の最初の素数.

アドバイスをいただければ幸いです。私は 2.7 Python を使用しています。

a = [2,3,5,7,11]
while 1:
    b = input('Enter the number for which all previous shall be tested for primality: ')
    c = len(a)
    d = 0
    isprime = True
    while b<=a[c-1] and not d==c:
            if b==a[d]:
            print a[0:d]
        if d==(c-1) and not b==a[d]:
            break
        d = d + 1
    while b>a[c-1]:
        d = 0
        print a[c-1]
        if b%a[d]==0:
            isprime = False
            break
        while a[d]==a[c-1]:
            f = a[c-1] + 2
            for g in range(f,b,2):
                if b%g==0:
                    isprime = False
                    break
            if isprime:
                a.append(b)
                print a

素数が見つかると、それらが保存され、次の素数のセットに使用されるように、このプログラムが機能するようにしました。これで、1000 までの素数を見つけたいとしましょう。プログラムは素数を計算します。では、2000 までの素数を知りたい。まあ、プログラムは 1000 までの素数を既に見つけているので、それらを再現する必要はないので、最大数以下の素数をすべて入力します。 、次に、新しい数を既知の素数で割って、残っているものを見つけます。次に、新しい素数を a に追加し、続行します。

唯一のことは、問題があるということです。私が計画したようには動作したくありません。修正に取り組んでいます。たぶん、あなたたちは参加して、何が悪いのかを見ることができますか?

よし、コードを編集して、より高速に実行できるようにしました。

While 1:
    i=input('Enter the number for which all previous shall be tested for primality: ')
    n=0
    while n<=i:
        n=n+1
        a=int(n**.5)
        for b in range(2,n):
            if n%b==0:
                break
             if b==a:
                print n
                break

これまでのところ、このプログラムは私のオリジナルと私が試したものよりもわずかな時間で実行されます。私が実行したテストでは、最初のアルゴリズムで 100000 までのすべての素数を見つけました。私の最初のアルゴリズムは、約 1 分 40 秒かかった私の新しいプログラムとは異なり、4 分以上かかりました。自分で言うのもなんですが、かなりのアップグレードです。

4

2 に答える 2

1

さまざまな素数アルゴリズムがありますが、そのうち sieve が最も高速です。c で python を拡張することに慣れている場合は、 primesieveをラップできます。以下はEratosthenes のふるいのpython 実装です。さらに問題がある場合はお知らせください。

from __future__ import generators
def eratosthenes():
    '''Yields the sequence of prime numbers via the Sieve of Eratosthenes.'''
    D = {}  # map composite integers to primes witnessing their compositeness
    q = 2   # first integer to test for primality
    while 1:
        if q not in D:
            yield q        # not marked composite, must be prime
            D[q*q] = [q]   # first multiple of q not already marked
        else:
            for p in D[q]: # move each witness to its next multiple
                D.setdefault(p+q,[]).append(p)
            del D[q]       # no longer need D[q], free memory
        q += 1
于 2013-03-10T18:24:28.390 に答える
-1

これはより速く動作するはずです：

while 1:
    i=input('Enter the number for which all previous shall be tested for primality: ')
    n=5
    a=[2,3]
    while n<=i:
        n=n+1
        isPrime = True
        for b in a:
            if n%b==0:
                isPrime = False
                break
        if isPrime:
            a.append(n)
            print a

しかし、より高度なアルゴリズムと非常に巨大な 10**100 を使用している場合を除いて、O(sebastian のコメントを参照) よりもはるかに高速になるとは思いません。

数値が大きくなると、常に遅くなります。

于 2013-03-10T11:14:03.440 に答える