Eratosties篩-尋找Python的Primes我只想澄清一點，這不是家庭作業的問題：)我想為我正在構建的數學應用程序找到素數&偶然發現的。埃拉托斯提尼篩接近。我已經用Python編寫了它的實現。但速度太慢了。比方說，如果我想找到不到200萬的素數。需要超過20分鐘。(我在這一點上停止了它)。我怎么才能加快速度？def primes_sieve(limit):
limitn = limit+1
primes = range(2, limitn)
for i in primes:
factors = range(i, limitn, i)
for f in factors[1:]:
if f in primes:
primes.remove(f)
return primesprint primes_sieve(2000)最新情況：最后，我對這段代碼進行了分析&發現在從列表中刪除元素上花費了相當多的時間。考慮到它必須遍歷整個列表(最壞的情況)來查找元素&然后刪除它，然后重新調整列表，這是完全可以理解的(也許會有一些副本繼續嗎？)不管怎么說，我把字典的單子扔掉了。我的新計劃-def primes_sieve1(limit):
limitn = limit+1
primes = dict()
for i in range(2, limitn): primes[i] = True
for i in primes:
factors = range(i,limitn, i)
for f in factors[1:]:
primes[f] = False
return [i for i in primes if primes[i]==True]print primes_sieve1(2000000)
3 回答
海綿寶寶撒
TA貢獻1809條經驗 獲得超8個贊
primes_sieve
primes_sieve1
def primes_sieve2(limit): a = [True] * limit # Initialize the primality list a[0] = a[1] = False for (i, isprime) in enumerate(a): if isprime: yield i for n in range(i*i, limit, i): # Mark factors non-prime a[n] = False
i*i
慕姐8265434
TA貢獻1813條經驗 獲得超2個贊
def eratosthenes(n): multiples = [] for i in range(2, n+1): if i not in multiples: print (i) for j in range(i*i, n+1, i): multiples.append(j)eratosthenes(100)
米脂
TA貢獻1836條經驗 獲得超3個贊
def primes_sieve(limit): limitn = limit+1 not_prime = set() primes = [] for i in range(2, limitn): if i in not_prime: continue for f in range(i*2, limitn, i): not_prime.add(f) primes.append(i) return primesprint primes_sieve(1000000)
def primes_sieve(limit): limitn = limit+1 not_prime = [False] * limitn primes = [] for i in range(2, limitn): if not_prime[i]: continue for f in xrange(i*2, limitn, i): not_prime[f] = True primes.append(i) return primes
添加回答
舉報
0/150
提交
取消