Is there a simple algorithm that can determine if X is prime?

I have been trying to work my way through Project Euler, and have noticed a handful of problems ask for you to determine a prime number as part of it.

1. I know I can just divide x by 2, 3, 4, 5, ..., square root of X and if I get to the square root, I can (safely) assume that the number is prime. Unfortunately this solution seems quite klunky.

2. I've looked into better algorithms on how to determine if a number is prime, but get confused fast.

Is there a simple algorithm that can determine if X is prime, and not confuse a mere mortal programmer?

Thanks much!

The first algorithm is quite good and used a lot on Project Euler. If you know the maximum number that you want you can also research Eratosthenes's sieve.

If you maintain the list of primes you can also refine the first algo to divide only with primes until the square root of the number.

With these two algoritms (dividing and the sieve) you should be able to solve the problems.

Edit: fixed name as noted in comments

To generate all prime numbers less than a limit Sieve of Eratosthenes (the page contains variants in 20 programming languages) is the oldest and the simplest solution.

In Python:

def iprimes_upto(limit):
    is_prime = [True] * limit
    for n in range(2, limit):
        if is_prime[n]:
           yield n
           for i in range(n*n, limit, n): # start at ``n`` squared
               is_prime[i] = False

Example:

>>> list(iprimes_upto(15))
[2, 3, 5, 7, 11, 13]

I see that Fermat's primality test has already been suggested, but I've been working through Structure and Interpretation of Computer Programs, and they also give the Miller-Rabin test (see Section 1.2.6, problem 1.28) as another alternative. I've been using it with success for the Euler problems.

Here's a simple optimization of your method that isn't quite the Sieve of Eratosthenes but is very easy to implement: first try dividing X by 2 and 3, then loop over j=1..sqrt(X)/6, trying to divide by 6*j-1 and 6*j+1. This automatically skips over all numbers divisible by 2 or 3, gaining you a pretty nice constant factor acceleration.

Keeping in mind the following facts (from MathsChallenge.net):

• All primes except 2 are odd.
• All primes greater than 3 can be written in the form 6k - 1 or 6k + 1.
• You don't need to check past the square root of n

Here's the C++ function I use for relatively small n:

bool isPrime(unsigned long n)
{
    if (n == 1) return false; // 1 is not prime
    if (n < 4) return true; // 2 and 3 are both prime
    if ((n % 2) == 0) return false; // exclude even numbers
    if (n < 9) return true; //we have already excluded 4, 6, and 8.
    if ((n % 3) == 0) return false; // exclude remaining multiples of 3

    unsigned long r = floor( sqrt(n) );
    unsigned long f = 5;
    while (f <= r)
    {
        if ((n % f) == 0)  return false;
        if ((n % (f + 2)) == 0) return false;
        f = f + 6;
    }
    return true; // (in all other cases)
}

You could probably think of more optimizations of your own.