總理計算丟失首任

Question

請幫我解決我的代碼這是應該使用數字因子篩來確定素數：

def primeNumbers(num): 
    primes = [] 
    i = 2 
    # iterates through range from 2 to num(inclusive) 
    while i <= num :  # add 'while' condition 
     k = 2 
     isPrime = True 
     # check if prime number 
     while k * k < num :  # add 'while' condition 
     if i%k==0: 
     isPrime = False 
      k +=1   # update k 
     if isPrime: 
      primes.append(i) 

     i +=1    # update i 
    return primes 

Answer 1

試試這個判斷素數（using sieve algorithm） ：

def primes(n): 
    if n==2: return [2] 
    elif n<2: return [] 
    s=range(3,n+1,2) 
    mroot = n ** 0.5 
    half=(n+1)/2-1 
    i=0 
    m=3 
    while m <= mroot: 
     if s[i]: 
     j=(m*m-3)/2 
     s[j]=0 
     while j<half: 
      s[j]=0 
      j+=m 
     i=i+1 
     m=2*i+3 
    return [2]+[x for x in s if x] 

print primes(5) 
# prints: [2, 3, 5] 

Answer 2

這裏是你的函數最小的解決辦法：

def primeNumbers(num): 
    primes = [] 
    i = 2 
    while i <= num: 
     k = 2 
     isPrime = True 
     while k*k <= i: 
      if i%k == 0: 
       isPrime = False 
      k += 1 
     if isPrime: 
      primes.append(i) 
     i += 1 
    return primes 

重要的改變是測試while k*k <= i，它取代while k*k < num。

請注意，也可以進行多項效率改進（例如，在將isPrime設置爲False並僅檢查素數因子時，從循環中斷開），但這應該會給出正確的結果。