Is there a Python library to list primes?

Question

Is there a library function that can list primes (in sequence) in Python?

I found this question. The quickest way to list all primes below N , but I would prefer to use someone else's reliable library, except for the movie. I would be happy to do import math; for n in math.primes: import math; for n in math.primes:

Answer 1

The gmpy2 library has a function next_prime (). This simple function will create a generator that provides an infinite supply of primes:

 import gmpy2 def primes(): n = 2 while True: yield n n = gmpy2.next_prime(n) 

If you search for primes repeatedly, creating and reusing a table of all primes below a reasonable limit (e.g. 1,000,000) will be faster. Here is another example of using gmpy2 and Eratosthenes sieve to create a prime table. primes2 () first returns the numbers from the table, and then uses next_prime ().

 import gmpy2 def primes2(table=None): def sieve(limit): sieve_limit = gmpy2.isqrt(limit) + 1 limit += 1 bitmap = gmpy2.xmpz(3) bitmap[4 : limit : 2] = -1 for p in bitmap.iter_clear(3, sieve_limit): bitmap[p*p : limit : p+p] = -1 return bitmap table_limit=1000000 if table is None: table = sieve(table_limit) for n in table.iter_clear(2, table_limit): yield n n = table_limit while True: n = gmpy2.next_prime(n) yield n 

You can customize table_limit to suit your needs. Larger values ​​will require more memory and increase startup time for the first call to primes (), but it will be faster for repeated calls.

Note. I support gmpy2.

Answer 2

SymPy is another choice. This is a Python library for symbolic math. It provides several features for easy.

 isprime(n) # Test if n is a prime number (True) or not (False). primerange(a, b) # Generate a list of all prime numbers in the range [a, b). randprime(a, b) # Return a random prime number in the range [a, b). primepi(n) # Return the number of prime numbers less than or equal to n. prime(nth) # Return the nth prime, with the primes indexed as prime(1) = 2. The nth prime is approximately n*log(n) and can never be larger than 2**n. prevprime(n, ith=1) # Return the largest prime smaller than n nextprime(n) # Return the ith prime greater than n sieve.primerange(a, b) # Generate all prime numbers in the range [a, b), implemented as a dynamically growing sieve of Eratosthenes. 

Here are some examples.

 >>> import sympy >>> >>> sympy.isprime(5) True >>> list(sympy.primerange(0, 100)) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] >>> sympy.randprime(0, 100) 83 >>> sympy.randprime(0, 100) 41 >>> sympy.prime(3) 5 >>> sympy.prevprime(50) 47 >>> sympy.nextprime(50) 53 >>> list(sympy.sieve.primerange(0, 100)) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] 

Answer 3

Asking this question, I wrote a Python wrapper around the C ++ library. https://github.com/hickford/primesieve-python

 >>> from primesieve import * # Generate a list of the primes below 40 >>> generate_primes(40) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] # Generate a list of the primes between 100 and 120 >>> generate_primes(100, 120) [101, 103, 107, 109, 113] # Generate a list of the first 10 primes >>> generate_n_primes(10) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] # Generate a list of the first 10 starting at 1000 >>> generate_n_primes(10, 1000) [1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061] # Get the 10th prime >>> nth_prime(10) 29 # Count the primes below 10**9 >>> count_primes(10**9) 50847534 

Answer 4

There is no constant time algorithm for generating the next prime number; therefore, most libraries require an upper bound. This is actually a huge problem that needs to be solved for digital cryptography. RSA selects large enough primes, choosing a random number and testing for primitiveness until it finds a prime.

For an arbitrary integer N only way to find the next prime after N is to iterate through N+1 to an unknown prime P test for simplicity.

Testing for primitiveness is very cheap, and there are python libraries that do this: AKS Primes Algorithm in Python

For the test_prime function, than the iterator of infinite primes, it will look something like this:

 class IterPrimes(object): def __init__(self,n=1): self.n=n def __iter__(self): return self def next(self): n = self.n while not test_prime(n): n += 1 self.n = n+1 return n 

There are many heuristics that you could use to speed up the process. For example, skip even numbers or numbers divisible by 2,3,5,7,11,13, etc.