Python素數生成器

Question

該代碼打印每個非素數兩次，但只打印一次素數。 但是，我只想要打印出素數。 我知道有更好的解決方案的素數生成器，但我真的想知道這個代碼中的錯誤在哪裏。

prime_numbers = [] 

def prime_gen(upper_limit): 
    for i in range(2, upper_limit): 
     for j in range(2, upper_limit): 
      if i % j == 0 and i % j != 1 and i % j != j and i: 
       prime_numbers.append(i) 
prime_gen(20) 
print(prime_numbers) 

Answer 1

你應該i停止j，沒有上限。找不到i的因子大於i - 沒有任何意義。而且它本身不應該被測試，因爲它總是自我分化。

而且一個數不是素數，因爲它可以被另一個整除，但因爲它不是。因此，測試全部可能的除數，並且只有在末尾沒有找到時，纔將i添加到素數列表中。

prime_numbers = [] 

def prime_gen(upper_limit): 
    for i in range(2, upper_limit): 
     for j in range(2, i):    # <== only look for divisors less than i 
      if i % j == 0:    # <== STOP if you found a divisor 
       break 
     else:        # <== Add only if no divisor was found 
      prime_numbers.append(i) 
prime_gen(20) 
print(prime_numbers) 

Answer 2

prime_numbers = [2] # we know two is prime 
def prime_gen(upper_limit): 
    # start at 3 and use a step of 2 
    for i in range(3, upper_limit, 2): 
     # loop from 2 to i 
     for j in range(2, i): 
      # if i was divisible by any j we will break the loop 
      # as i is not prime 
      if i % j == 0: 
       break 
     else: 
      # if we get here we completed our inner loop 
      # which means no i % j was equal to 0 
      prime_numbers.append(i) 

您需要的內環2去我，你不想滿足if i % j == 0因爲這些都不是素數。你最後的and i也總是爲真，任何非0的數字都將爲真，所以測試是多餘的。你也可以從3開始，使用2的步驟，所有的偶數不能是素數。

您還可以在if/else與any:這將延遲計算的，如果我們發現等於0

prime_numbers = [2] 

def prime_gen(upper_limit): 
    for i in range(3, upper_limit, 2): 
     if not any(i % j == 0 for j in range(2, i)): 
      prime_numbers.append(i) 

Answer 3

第一個是沒有任何優化，打破i % j替換，而第二個稍微更優化。當然，「Sieve of Eratosthenes」是最好的。這個函數按順序產生素數，但沒有上限。

簡單，沒有優化：

def simple_prime_list(num): 
    list_of_prime = (2,) 
    current_num = 2 
    is_prime = True 
    while len(list_of_prime) != num: 
     current_num += 1 
     for i in list_of_prime: 
      if current_num % i == 0: 
       is_prime = False 
     if is_prime == True: 
      list_of_prime += (current_num,) 
     #To reset the status 
     is_prime = True 
    return list_of_prime 

通過不檢查所有的偶數和break出的for循環時數是不是質略優化：

def prime_list(num): 
    list_of_prime = (2,) 
    current_num = 2 
    is_prime = True 
    while len(list_of_prime) != num: 
     current_num += 1 
     if current_num % 2 != 0: 
      for i in list_of_prime: 
       if current_num % i == 0: 
        is_prime = False 
        break 
      if is_prime == True: 
       list_of_prime += (current_num,) 
     #To reset the status 
     is_prime = True 
    return list_of_prime 

嘗試測量2不同的運行時間：

import time 
def measureTime(fn): 
    start = time.clock() 
    fn() 
    end = time.clock() 
    #return value in millisecond 
    return (end - start)*1000 

print('Simple Prime List:', measureTime(lambda: simple_prime_list(1000)), 'ms') 
print('Optimised Prime List:', measureTime(lambda: prime_list(1000)), 'ms') 

輸出：

簡單總理名單：775.798毫秒

優化總理名單：69.48299999999996毫秒