計算素數並追加到列表

Question

我最近開始嘗試使用python解決項目Euler上的問題，並且在嘗試計算素數並將它們附加到列表時遇到了這個道路顛簸。我寫了下面的代碼，但我很困惑，爲什麼它在運行時不輸出任何內容。

import math 

primes = [] 

def isPrime(i): 
    if number<=1: 
     return False 
    if number==2: 
     return True 
    if number%2==0: 
     return False 
    for i in range(3,int(sqrt(number))+1): 
     if number%i==0: 
      return False 
    return True 

for i in range (1, 9999999): 
    if isPrime(i) == True: 
     primes.append(i) 
    else: 
     continue 
print(primes) 

Answer 1

嘗試：

import math 

primes = [] 

def isPrime(number): 
    if number<=1: 
     return False 
    if number==2: 
     return True 
    if number%2==0: 
     return False 
    for i in range(3,int(math.sqrt(number))+1): 
     if number%i==0: 
      return False 
    return True 

for i in range (1, 9999999): 
    if isPrime(i) == True: 
     primes.append(i) 

print(primes) 

Answer 2

試試這個：

import math 

primes = [] 

def isPrime(number): 
    if number<=1: 
     return False 
    if number==2: 
     return True 
    if number%2==0: 
     return False 
    for ind in range(3,int(math.sqrt(number))+1): 
     if number%ind==0: 
      return False 
    return True 

for i in range (1, 100): 
    if isPrime(i) == True: 
     primes.append(i) 
    else: 
     continue 

print(primes) 

要顯示它的工作，我打印的第100：

[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] 

Answer 3

使用條件列表理解：

primes = [ 
    i for i in range(1, 9999999) 
    if i == 2 
    or i > 2 # Anything less than 2 is not prime. 
    and i % 2 # No evens (except for 2 above) 
    and all(i % n for n in range(3, int(i ** 0.5) + 1))] 

>>> primes[:10] 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29] 

>>> primes[-10:] 
[9999889, 
9999901, 
9999907, 
9999929, 
9999931, 
9999937, 
9999943, 
9999971, 
9999973, 
9999991] 

Answer 4

最簡單的方法是使用稱爲Sieve的東西。以下是如何使所有素數達到一百萬。

def mark_sieve(sieve, x): 
    for i in range(x+x, len(sieve), x): 
     sieve[i] = False 

sieve = [True]*(10**7+1) 
for x in range(2, int(len(sieve)**0.5 + 1)): 
    if sieve[x]: mark_sieve(sieve, x) 

的想法是，我們最初創建一個名爲sieve列表，並指定所有值True這意味着我們現在考慮所有的數字爲1萬美元（含）的素數。我們將遍歷每一個數字到一百萬，並在sieve列表中將其每個倍數標記爲False。另外，爲了優化，我們只迭代100萬的平方根。爲什麼這樣？因爲一個數字不能有兩個因素都大於數字的平方根。因此，如果我們將整數除以整數直到其平方根的上限，而且它仍然不可分割，那就意味着它是一個素數。

所以，如果你想檢查一個數字是否爲素數，你可以簡單地使用sieve[some_number]。如果它返回False它不是主要的。爲了獲得質數的列表，你可以使用[x for x in range(len(sieve)) if sieve[x]]

編輯 速度比較 -

import timeit 
import math 

def isPrime(number): 
    if number<=1: 
     return False 
    if number==2: 
     return True 
    if number%2==0: 
     return False 
    for ind in range(3,int(math.sqrt(number))+1): 
     if number%ind==0: 
      return False 
    return True 

def mark_sieve(sieve, x): 
    for i in range(x+x, len(sieve), x): 
     sieve[i] = False 


# Other approaches 
time_0 = timeit.default_timer() 
primes = [] 
for i in range (1, 10**6+1): 
    if isPrime(i) == True: 
     primes.append(i) 
    else: 
     continue 

# Sieve Approach 
time_1 = timeit.default_timer() 
sieve = [True]*(10**6+1) 
sieve[0] = False #because we wont consider zero and one as primes 
sieve[1] = False 
for x in range(2, int(len(sieve)**0.5 + 1)): 
    if sieve[x]: mark_sieve(sieve, x) 

primes_2 = [x for x in range(len(sieve)) if sieve[x]] 

time_2 = timeit.default_timer() 
time_1-time_0 # 12.423080921173096 seconds 
time_2-time_1 # 0.9901950359344482 seconds 

對於10萬個的數字，用篩快12倍以上。對於一百萬比例變爲90.而且，當使用這麼多數字時，我會建議不要追加列表。相反，啓動一個列表然後分配值。

Answer 5

如果您正在構建素數列表，將該列表用作解決方案的一部分效率會更高。

例如，這個循環：

for i in range(3, int(math.sqrt(number)) + 1): 

對於素1009將測試〜30個的數字，但只有10個素數小於1009的平方根實際上需要進行測試。而這種差異正在不斷增加。

使用我們的增長主要列表作爲解決方案的一部分：

primes = [2] 

for number in range(3, 9999999 + 1, 2): # only test odd numbers 

    for prime in primes: 
     if prime * prime > number: # we're past sqrt, a prime! 
      primes.append(number) 
      break 

     if number % prime == 0: # a composite 
      break 

print(*primes[:10], '...', *primes[-10:]) 

無處快@ ClockSlave的篩子，但許多其他的解決方案之前，將有可能完成。

Answer 6

現在它的工作原理，我已經shortned的編號，以999

import math 

primes = [] 


def isPrime(number): 
    if number <= 1: 
     return False 
    for i in range(2, int(math.sqrt(number)) + 1): 
     if number % i == 0: 
      return False 
    return True 

for i in range(1, 999): 
    if isPrime(i): 
     primes.append(i) 

print(primes) 

[OUTPUT]：

[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，34 7，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]

Answer 7

在[0,9999999]中獲得所有素數的算法效率不高。它需要花很長時間才能完成，以便在執行時不會看到輸出。這只是因爲它沒有完成。對於更快的算法，您可能會檢查this列出