primes.py

Prime number library for Python 3

If you want to help develop, open an issue or fork the repo, make your changes and submit a pull request.

Primes

A list-like object that automatically generates additional prime numbers as required. Supports membership testing and slicing for sequences of prime numbers

>>> primes = Primes()
>>> 10 in primes
False
>>> 11 in primes
True
>>> primes[10:20]
[31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
>>> primes[15:10:-2]
[53, 43, 37]
>>> primes[100]
547
>>> primes.index(23)
8

---

There are also a number of functions for prime generation and primality testing:

primes_up_to

Implementation of Sieve of Eratosthenes

Returns all primes up to (and including) x

Can pass in primes to decrease execution time

>>> primes_up_to(10)
[2, 3, 5, 7]

>>> primes_up_to(20, [2, 3, 5, 7])
[2, 3, 5, 7, 11, 13, 17, 19]

is_prime

Returns True if x is a prime number, False if it is not

Can pass in known primes to decrease execution time

>>> is_prime(191)
True

>>> is_prime(192)
False

n_primes

Returns the first n primes

Can pass in known primes to decrease execution time

>>> n_primes(5)
[2, 3, 5, 7, 11]

>>> n_primes(10, [2, 3, 5, 7, 11])
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

nth_prime

Returns the n^th prime (i.e. the 3^rd prime, the 6^th prime)

Can pass in known primes to decrease execution time

>>> nth_prime(1000)
7919

>>> nth_prime(4, [2, 3, 5, 7, 11])
7

composites_up_to

Returns all composite (non-prime greater than 1) numbers up to (and including) x

Can pass in known primes to decrease execution time

>>> composites_up_to(10)
[4, 6, 8, 9, 10]

>>> composites_up_to(20, [2, 3, 5, 7, 11, 13, 17, 19, 23])
[4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20]

next_prime

Given primes, returns the next prime

Uses method of trial division

This is much less efficient than primes_up_to for generating ranges of primes

>>> next_prime([2, 3, 5, 7, 11])
13

>>> next_prime(primesUpTo(1000000))
1000003