Generating primes of given length in python

Question

Is there any inbuilt function to generate a prime number of given binary length as Genprime in C++ NTL library ?

If not, then is it needed to check all numbers of given length until a prime number encounters ?

Answer 1

Well there's a complete ready-to-use package for it. Check https://pypi.python.org/pypi/pyprimes/

It contains implementations to popular efficient methods like Sieve of Eratosthenes, Croft Spiral, Wheel Factorisation etc and also contains functions for prime-test.

There are also interesting threads on prime number generation on StackOverflow. Check:

Fastest way to list all primes below N

Simple Prime Generator in Python

Answer 2

If the numbers are small, less than about 10^9, a segmented Sieve of Eratosthenes can be used to generate prime numbers over a range. If the numbers are larger, you will need to test odd numbers for primality. It's not hard to write a primality checker:

def isPrime(n, k=5): # miller-rabin
    from random import randint
    if n < 2: return False
    for p in [2,3,5,7,11,13,17,19,23,29]:
        if n % p == 0: return n == p
    s, d = 0, n-1
    while d % 2 == 0:
        s, d = s+1, d/2
    for i in range(k):
        x = pow(randint(2, n-1), d, n)
        if x == 1 or x == n-1: continue
        for r in range(1, s):
            x = (x * x) % n
            if x == 1: return False
            if x == n-1: break
        else: return False
    return True

It's easy to search for the next prime by considering each successive odd number as a candidate and testing it with the isPrime function. But number theory tells us that all primes greater than 5 must be of the form 30k±1, 30k±7, 30k±11 or 30k±13 for some non-negative integer k, so you can double the speed of the nextPrime function by eliminating half of the odd candidates before the primality test:

def nextPrime(n):
    if n < 2: return 2
    if n < 3: return 3
    if n < 5: return 5
    n = n + 1 if n % 2 == 0 else n + 2
    while not isPrime(n):
        n += [1,6,5,4,3,2,1,4,3,2,1,2,1,4,3,2,1, \
              2,1,4,3,2,1,6,5,4,3,2,1,2][n % 30]
    return n

As a simple check, we note there are 78498 primes less than a million (though if you want to generate all the primes in order, you should know that this will be much slower, by two or three orders of magnitude, than using a sieve):

>>> len, p = 0, 2
>>> while p < 1000000:
...     len += 1
...     p = nextPrime(p)
...
>>> len
78498

The nextPrime function works perfectly well on big numbers, which is what it is designed to do:

>>> nextPrime(12345678901234567890123456789012345678901234567890123)
12345678901234567890123456789012345678901234567890223L

If you're interested in programming with prime numbers, I modestly recommend this essay at my blog.