2

可能重复：
在python中列出N以下所有素数的最快方法

很久没做编程了，做这个纯粹是为了好玩，对高级Python也不是很了解，但是……我写了这个，想知道是不是真的是Eratosthenes Sieve程序，如果是，我怎样才能让它更快。我真的不希望有人发布一个解决方案，但更多告诉我如何调整我的。

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

谢谢你的帮助。

顺便说一句 - 它在 Python 2.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）

此外，第二个的范围for是错误的，因为您考虑的是列表的长度，而不是当前值，b因此您仅在前 50 个值中检查 2 的倍数，在前 17 个中检查 3 的倍数，5 在前 9 个，以此类推。从b = 13你永远不会进入内在for，因为int(round(len(all)/b)) = 1你有类似的东西for i in range(2,1)

于 2012-12-14T14:14:03.000 回答
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 回答
0

我同意 Gianluca 的观点，我有一个可能的解决方案：将主数组 ( all) 保留为布尔值并标记非素数，但不要删除它们。它也可能更快，因为您不会更改列表大小。

小事：all = range(2, n+1)如果你想把它保留为整数，你可以在开头写。

于 2012-12-14T14:52:04.190 回答
-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 回答