What is the best algorithm for checking if a numbe

Question

Just an example of what I am looking for: I could represent every odd number with a 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 eleminate multiples of five with some work, but numbers that end with 1, 3, 7 or 9 must be there in the array of bits. Hope this would clarify what I want.

I am looking for the best algorithm, to check if a number is prime i.e. a boolean function:

bool isprime(number);

I would like to know the best algorithm to implement this functionality. Naturally, 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.

Answer 1

In Python 3:

def is_prime(a):
    if a < 2:
        return False
    elif a!=2 and a % 2 == 0:
        return False
    else:
        return all (a % i for i in range(3, int(a**0.5)+1))

Explanation: A prime number is a number only divisible by itself and 1. Ex: 2,3,5,7...

1) if a<2: if "a" is less than 2 it is not a prime.

2) elif a!=2 and a % 2 == 0: if "a" is divisible by 2 then its definitely not a prime. But if a=2 we don't want to evaluate that as it is a prime number. Hence the condition a!=2

3) return all (a % i for i in range(3, int(a0.5)+1) ):** First look at what all() command does in python. Starting from 3 we divide "a" till its square root (a**0.5). If "a" is divisible the output will be False. Why square root? Let's say a=16. The square root of 16 = 4. We don't need to evaluate till 15. We only need to check till 4 to say that it's not a prime.

Extra: A loop for finding all the prime number within a range.

for i in range(1,100):
    if is_prime(i):
        print("{} is a prime number".format(i))

Answer 2

One can use sympy.

import sympy

sympy.ntheory.primetest.isprime(33393939393929292929292911111111)

True

From sympy docs. The first step is looking for trivial factors, which if found enables a quick return. Next, if the sieve is large enough, use bisection search on the sieve. For small numbers, a set of deterministic Miller-Rabin tests are performed with bases that are known to have no counterexamples in their range. Finally if the number is larger than 2^64, a strong BPSW test is performed. While this is a probable prime test and we believe counterexamples exist, there are no known counterexamples

Answer 3

According to wikipedia, the Sieve of Eratosthenes has complexity O(n * (log n) * (log log n)) and requires O(n) memory - so it's a pretty good place to start if you aren't testing for especially large numbers.

Answer 4

The best method, in my opinion, is to use what's gone before.

There are lists of the first N primes on the internet with N stretching up to at least fifty million. Download the files and use them, it's likely to be much faster than any other method you'll come up with.

If you want an actual algorithm for making your own primes, Wikipedia has all sorts of good stuff on primes here, including links to the various methods for doing it, and prime testing here, both probability-based and fast-deterministic methods.

There should be a concerted effort to find the first billion (or even more) primes and get them published on the net somewhere so people can stop doing this same job over and over and over and ... :-)

Answer 5

There are many ways to do the primality test.

There isn't really a data structure for you to query. If you have lots of numbers to test, you should probably run a probabilistic test since those are faster, and then follow it up with a deterministic test to make sure the number is prime.

You should know that the math behind the fastest algorithms is not for the faint of heart.