Checking if a number is prime in Python [duplicate]

Question

Naturally, for bool isprime(number) there would be a data structure I could query.
I define the best algorithm, to be the algorithm that produces a data structure with lowest memory consumption for the range (1, N], where N is a constant.
Just an example of what I am looking for: I could represent every odd number with one bit e.g. for the given range of numbers (1, 10], starts at 3: 1110

The following dictionary can be squeezed more, right? I could eliminate multiples of five with some work, but numbers that end with 1, 3, 7 or 9 must be there in the array of bits.

How do I solve the problem?

Answer 1

The fastest algorithm for general prime testing is AKS. The Wikipedia article describes it at lengths and links to the original paper.

If you want to find big numbers, look into primes that have special forms like Mersenne primes.

The algorithm I usually implement (easy to understand and code) is as follows (in Python):

def isprime(n):     """Returns True if n is prime."""     if n == 2:         return True     if n == 3:         return True     if n % 2 == 0:         return False     if n % 3 == 0:         return False      i = 5     w = 2      while i * i <= n:         if n % i == 0:             return False          i += w         w = 6 - w      return True 

It's a variant of the classic O(sqrt(N)) algorithm. It uses the fact that a prime (except 2 and 3) is of form 6k - 1 or 6k + 1 and looks only at divisors of this form.

Sometimes, If I really want speed and the range is limited, I implement a pseudo-prime test based on Fermat's little theorem. If I really want more speed (i.e. avoid O(sqrt(N)) algorithm altogether), I precompute the false positives (see Carmichael numbers) and do a binary search. This is by far the fastest test I've ever implemented, the only drawback is that the range is limited.

Answer 2

A pretty simple and concise brute-force solution to check whether a number N is prime: simply check if there is any divisor of N from 2 up to the square root of N (see why here if interested).

The following code is compatible with both Python 2 and Python 3:

from math import sqrt from itertools import count, islice  def is_prime(n):     return n > 1 and all(n % i for i in islice(count(2), int(sqrt(n) - 1))) 

And here's a simpler Python 3 only implementation:

def is_prime(n):     return n > 1 and all(n % i for i in range(2, int(n ** 0.5) + 1)) 

Here are the extended versions of the above for clarity:

from math import sqrt from itertools import count, islice  def is_prime(n):     if n < 2:         return False      for divisor in islice(count(2), int(sqrt(n) - 1)):         if n % divisor == 0:             return False      return True 

def is_prime(n):     if n < 2:         return False      for divisor in range(2, int(n ** 0.5) + 1):         if n % divisor == 0:             return False      return True 

This is not meant to be anything near the fastest nor the most optimal primality check algorithm, it only accomplishes the goal of being simple and concise, which also reduces implementation errors. It has a time complexity of O(sqrt(n)).

If you are looking for faster algorithms to check whether a number is prime, you might be interested in the following:

• Finding primes & proving primality: brief overview and explanation of the most famous primality tests and their history.
• Probabilistic primality tests (Wikipedia): these can be incorporated in the above code rather easily to skip the brute force if they do not pass, as an example there is this excellent answer to the duplicate of this question.
• Fast deterministic primaliry tests (Wikipedia)
• This Q&A Fastest way to list all primes below N along with the pyprimesieve library.

---

Implementation notes

You might have noticed that in the Python 2 compatible implementation I am using itertools.count() in combination with itertools.islice() instead of a simple range() or xrange() (the old Python 2 generator range, which in Python 3 is the default). This is because in CPython 2 xrange(N) for some N such that N > 2⁶³ ‒ 1 (or N > 2³¹ ‒ 1 depending on the implementation) raises an OverflowError. This is an unfortunate CPython implementation detail.

We can use itertools to overcome this issue. Since we are counting up from 2 to infinity using itertools.count(2), we'll reach sqrt(n) after sqrt(n) - 1 steps, and we can limit the generator using itertools.islice().