如何查找給定範圍內的所有素數？

Question

def all primes(start,end): 
    list_primes = [] 
    for i in range(start,end): 
     for a in range(2,i): 
      if i % a == 0: 
       list_primes.append(i) 

    return list_primes 

出於某種原因，它返回的只是素數。它可能是一些愚蠢的錯誤。誰能幫忙？

Answer 1

你只添加素數，直到i - 1它從來沒有除數。因此，對於 2的所有'a'，直到i - 1 if(i % a == 0)評估爲false。

if(i % a == 0)if(i % a == 0)對'a'和'i'的評估結果不是素數。因此，你停下來，再換一個'我'。

Answer 2

您內環更改爲：

for a in range(2,i): 
    if i % a == 0: 
     break 
else: 
    list_primes.append(i) 

複製從here :-)
順便粘貼，他們用例如相同的代碼:)

Answer 3

你可以試試這個功能

def generate_primes(lower_limit,upper_limit): 
    if not isprime(lower_limit): 
     return False 
    candidate = lower_limit 
    r = [] 
    while(candidate <= upper_limit): 
     trial_divisor = 2 
     prime = 1 # assume it's prime 
     while(trial_divisor**2 <= candidate and prime): 
      if(candidate%trial_divisor == 0): 
       prime = 0 # it isn't prime 
      trial_divisor+=1 
     if(prime): 
      r += [candidate] 
     candidate += 2 
    return r 

def isprime(n): 
    '''check if integer n is a prime''' 
    # make sure n is a positive integer 
    n = abs(int(n)) 
    # 0 and 1 are not primes 
    if n < 2: 
     return False 
    # 2 is the only even prime number 
    if n == 2: 
     return True  
    # all other even numbers are not primes 
    if not n & 1: 
     return False 
    # range starts with 3 and only needs to go up the squareroot of n 
    # for all odd numbers 
    for x in range(3, int(n**0.5)+1, 2): 
     if n % x == 0: 
      return False 
    return True 

我對此頁進行了修改http://dunningrb.wordpress.com/2009/02/12/prime-numbers-and-a-simple-python-code/

Answer 4

試試這個：

def isprime (x): 
    isprime=True 
    if x!=2: 
     for i in range (2,x): 
      if x%2==0: 
       isprime=False 
      break 
     return isprime 
x=int(input("enter a number")) 
z=isprime(x) 
print(z) 

Answer 5

試試這個（使用篩埃拉托色尼的）：

def all_primes(start, end): 
     return list(sorted(set(range(start,end+1)).difference(set((p * f) for p in range(2, int(end ** 0.5) + 2) for f in range(2, (end/p) + 1))))) 

Answer 6

爲了得到質數，嘗試實現埃拉托色尼算法的篩https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

在Python 3尋求在100萬的數字中，對我而言大約需要0.5秒

def get_primes(start, stop): 
    dct = {x: True for x in list(range(start, stop+1))} 
    x = start 

    while x ** 2 <= stop: 
     if dct[x]: 
      y = x ** 2 
      while y <= stop: 
       dct[y] = False 
       y += x 
     x += 1 

    lst = [] 
    for x, y in dct.items(): 
     if y: 
      lst.append(x) 

    return lst 

res = get_primes(2, 1000000) 
print(res) 

Answer 7

我想和大家分享的是我發現的範圍內產生質數的最快方法是使用SymPy symbolic mathematics library：

import sympy 

def all_primes(start, end): 
    return list(sympy.sieve.primerange(start, end)) 

的sympy.sieve.primerange()函數返回一個發電機，所以我們需要list()將其轉換爲一個列表。

下面是已經很優化的回答這個之間的性能差異，以及一個例子是目前最upvoted在這個線程：

import sympy 

def get_primes_python(start, stop): 
    dct = {x: True for x in list(range(start, stop+1))} 
    x = start 

    while x ** 2 <= stop: 
     if dct[x]: 
      y = x ** 2 
      while y <= stop: 
       dct[y] = False 
       y += x 
     x += 1 

    lst = [] 
    for x, y in dct.items(): 
     if y: 
      lst.append(x) 

    return lst 

def get_primes_sympy(start, stop): 
    return list(sympy.sieve.primerange(start, stop)) 

In [2]: %timeit test.get_primes_python(1, 10**7) 
1 loop, best of 3: 4.21 s per loop 

In [3]: %timeit test.get_primes_sympy(1, 10**7) 
10 loops, best of 3: 138 ms per loop