How to find all primes in a given range?

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 

For some reason, it returns everything except prime numbers. It was probably a stupid mistake. Can anyone help?

Answer 1

Change your inner loop to:

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

Copy from here :-)
By the way, they used the same code, for example :)

Answer 2

Try this (uses the Sieve of Eratosthenes):

  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 3

For prime numbers, try implementing the Sieve of Eratosthenes algorithm https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

In Python 3, to search in 1 million numbers, I need about 0.5 seconds

 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 4

You add only a stroke if before i - 1 it never had a divisor. Thus, for all "a" from 2 until I - 1 if(i % a == 0) is false.

And if(i % a == 0) evaluates true for 'a' other than 'i' is not simple. So you stop it for and take another "i".

Answer 5

you can try this function

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

I changed it from this page http://dunningrb.wordpress.com/2009/02/12/prime-numbers-and-a-simple-python-code/

Answer 6

Try the following:

 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 7

I would like to share the fact that the fastest way with which I found generating prime numbers in a range is to use the sympy symbolic library :

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

The sympy.sieve.primerange() function returns a generator, so we need list() convert it to a list.

Here is an example of the performance difference between this and the already highly optimized answer that is currently most supported in this thread:

 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