0

200 万未満のすべての素数の合計を計算しようとしています。特定の数未満の素数を見つける関数を既に作成しているので、古い関数を呼び出して合計する新しい関数を単純に作成しました。そのリストの項目。

しかし、それは永遠にかかるようです。このコードを高速化するにはどうすればよいですか?

def find_primes(n):
    "Find the prime numbers below n"
    primes=[];
    for i in range(2,n):
        for fac in range (2,i):
            if i!=fac and i%fac == 0:
                break
        else:
            primes.append(i)
    return primes

def add_primes(m):
    "Sum all the prime numbers below m"
    newlist=find_primes(m);
    t=sum(newlist);
    return t

PS: 私は Python の初心者なので、間違いをうまく説明していただければ幸いです。前もって感謝します。

4

2 に答える 2

3

エラトステネスのふるいを実装します。これにより、コードが現在実行しているよりもはるかに少ない作業を実行できるようになり、はるかに高速になります。

于 2013-03-24T13:59:08.540 に答える
0

fac in range (2,i)for行を次のように置き換えることで、現在のコードを改善できます。

for fac in primes:

コード：

def find_primes1(n):
    "Find the prime numbers below n"
    primes=[2,3]     #initialize primes with 2 values
    for i in range(4,n):
        for fac in primes:
            if i!=fac and i%fac == 0:
                break
        else:
            primes.append(i)
    return primes

タイミング比較:

In [6]: %timeit find_primes(10**4)   # your version
1 loops, best of 3: 2.33 s per loop

In [7]: %timeit find_primes1(10**4)
1 loops, best of 3: 171 ms per loop

In [8]: find_primes1(10**3)==find_primes(10**3)
Out[8]: True

しかし、より大きな値については、間違いなくエラトステネスの篩法を学ぶ必要があります.

于 2013-03-24T14:08:45.597 に答える