2

重複の可能性：
PythonでNより下のすべての素数を一覧表示する最速の方法

私は長い間プログラミングをしていません、そして私はただ楽しみのためにこれをやっています、そして私はあまり高度なPythonを知りません、しかし...私はこれを書きました、そしてそれが実際にエラトステネスのふるいであるかどうか知りたいと思いましたプログラム、もしそうなら、どうすればもっと速くできますか？解決策となるプログラムを誰かに投稿してほしくないのですが、どうすれば自分のプログラムを適応させることができるかを教えてください。

def eratSieve(n):
    all = []
    for a in range(2, n+1):
        all.append(a)               
    for b in all:                       
        for i in range(2,int(round(len(all)/b))):
            while i*b in all:
                all.remove(i*b)
                i+=1
    return all

ご協力いただきありがとうございます。

ところで-それはPython2.7にあります

4

4 に答える 4

1

正しく動作しません。

主な問題は、のすべての値をループし、allからwhileいくつかの要素を削除することですall。

このように、の一部の値allは考慮されないため、関数はすべての非素数を削除しません

n = 100で実行してみると、次のようになります。

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99

あるべきですが

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 （http://en.wikipedia.org/wiki/Prime_numberから）

また、2番目の範囲forは間違っています。これは、リストの現在の値ではなくリストの長さを考慮しているbため、最初の50個の値でのみ2の倍数をチェックし、最初の17、5で3の倍数をチェックするためです。最初の9など。あなたからb = 13は決して内側forに入ることがないint(round(len(all)/b)) = 1ので、あなたは次のようなものを持っていますfor i in range(2,1)

于 2012-12-14T14:14:03.000 に答える
0

私はGianlucaに同意し、考えられる解決策があります。メイン配列（all）をboolとして保持し、非素数をマークしますが、それらを削除しないでください。リストのサイズを変更しないので、より高速になる場合もあります。

all = range(2, n+1)些細なこと： intとして保持したい場合は、最初に書くことができます。

于 2012-12-14T14:52:04.190 に答える
0

あなたの方法は間違った結果を生み出します。エラーはfor iループにあります。これが調整され、テストされています。

known_primes = [
2,3,5,7,11,13,17,19,23,29,
31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97,101,103,107,109,113,
127,131,137,139,149,151,157,163,167,173,
179,181,191,193,197,199,211,223,227,229,
233,239,241,251,257,263,269,271,277,281,
283,293,307,311,313,317,331,337,347,349,
353,359,367,373,379,383,389,397,401,409,
419,421,431,433,439,443,449,457,461,463,
467,479,487,491,499,503,509,521,523,541,
547,557,563,569,571,577,587,593,599,601,
607,613,617,619,631,641,643,647,653,659,
661,673,677,683,691,701,709,719,727,733,
739,743,751,757,761,769,773,787,797,809,
811,821,823,827,829,839,853,857,859,863,
877,881,883,887,907,911,919,929,937,941,
947,953,967,971,977,983,991,997,1009,1013,
1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,
1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,
1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,
1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,
1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,
1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,
1453,1459,1471,1481,1483,1487,1489,1493,1499]
def eratSieve(n):
    all = []
    for a in range(2, n+1):
        all.append(a)               
    for b in all:                       
        for i in all[all.index(b):]:
            while i*b in all:
                all.remove(i*b)
                i+=1
    return all

for N in range(1500):
    for n in eratSieve(N):
        if n not in known_primes:
            print N,n
于 2012-12-14T15:58:28.270 に答える
-1 
def primes(N):
    primes = [x for x in (2, 3, 5, 7, 11, 13) if x < N]
    if N < 17: return primes
    candidators = [x for x in xrange((N - 2) | 1, 15, -2)
                    if x % 3 and x % 5 and x % 7 and x % 11 and x % 13]
    top = int(N ** 0.5)
    while (top + 1) * (top + 1) <= N: top += 1
    while True:
        p = candidators.pop()
        primes.append(p)
        if p > top: break
        candidators = filter(p.__rmod__, candidators)
    candidators.reverse()
    primes.extend(candidators)
    return primes

このコードはもっと速く動作すると思います...

于 2012-12-14T14:10:10.787 に答える