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毫秒