Is there a Python library to list primes?

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

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.


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.


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]

Tags:

Python

Recent Posts