Is there a library function that can enumerate the prime numbers (in sequence) in Python?
I found this question Fastest way to list all primes below N but I'd rather use someone else's reliable library than roll my own. I'd be happy to do import math; for n in math.primes:
SymPy is another choice. It is a Python library for symbolic mathematics. It provides several functions for prime.
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]
The gmpy2 library has a next_prime() function. This simple function will create a generator that will provide an infinite supply of primes:
import gmpy2
def primes():
n = 2
while True:
yield n
n = gmpy2.next_prime(n)
If you will be searching through primes repeatedly, creating and reusing a table of all primes below a reasonable limit (say 1,000,000) will be faster. Here is another example using gmpy2 and the Sieve of Eratosthenes to create a table of primes. primes2() returns primes from the table first 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 adjust table_limit to suit your needs. Larger values will require more memory and increase the startup time for the first invocation of primes() but it will be faster for repeated calls.
Note: I am the maintainer of gmpy2.
Since asking this question, I wrote a Python wrapper around the C++ library primesieve, which went on to be adopted by the primesieve maintainer. https://github.com/kimwalisch/primesieve-python
Install from PyPi https://pypi.org/project/primesieve/ pip install primesieve
>>> 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
I needed the same thing and decided to create my own to excercise on many things.
Here: primes.py
WARNING: I tried to bugfix it as much as I could and making checks on everything, but I am still an amateur, so I do NOT guarantee advanced or professional checks and absence of bugs. Use at your own risk.
It will dynamically sieve primes numbers as needed, store them in a compressed binary format and retrieve them from there.
The most useful class is 'primes'. The class itself can be used as a generator, a container, subscripted and sliced.
WARNING: be careful iterating on infinite sequences!
from primes import primes
for p in primes: # 2, 3, 5, 7, 11, ...
pass
primes[0] # 2
primes[4] # 11
primes[1:6:2] # primes object, generates 3, 7, 13
7 in primes # True
8 in primes # False
'primes also has useful methods:
primes.estimate(1000) # 7830, real 1000th prime is 7927
primes.check(7) # True
primes.index_of(11) # 4 <- primes[4] = 11
primes.count_upto(10) # 4 <- len([2,3,5,7])
primes.sieve(5, 10) # [5, 7]
primes.in_range(5, 20, 2) # primes object, generates 5, 11, 13, 19
primes.factor(12) # {2:2, 3:1} <- 12 = 2^2 * 3^1
primes.phi(6) # 6 <- Euler phi function, number of smaller co-primes
And the primes objects are themselves generator, containers, subscriptable and sliceable, but on sublists of primes:
primerange1 = primes(1, None, 2) # generator
for p in primerange1: # 3, 7, 13, 19, ...
pass
primerange1[1] # 7
primerange1[:4:-1] # generator: 13, 7, 3
2 in primerange1 # False
primerange2 = primes(6, 0, -2) # generates 13, 7, 3
len(primerange2) # 3
reversed(primerange2) # primes object, generates 3, 7, 13
The class 'plib' is used to manage the library and its settings.
I hope someone will find it useful, and I'll be glad to receive any suggestion or bug report.
There is no constant time algorithm to generate the next prime number; this is why most libraries require an upper bound. This is actually a huge problem that needed to be solved for digital cryptography. RSA chooses sufficiently large primes by selecting a random number and testing for primality until it finds a prime.
Given an arbitrary integer N, the only way to find the next prime after N is to iterate through N+1 to the unknown prime P testing for primality.
Testing for primality is very cheap, and there are python libraries that do so: AKS Primes algorithm in Python
Given a function test_prime, than an infinite primes iterator will look something like:
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 a lot of heuristics you could use to speed up the process. For instance, skip even numbers, or numbers divisible by 2,3,5,7,11,13,etc..
https://pypi.org/project/primesieve/
Very fast compared to SymPy. I am using Python3 on Win10.
