Re: Fast efficient way to test a small number for primality?

From: rossum (rossum48_at_coldmail.com)
Date: 01/10/05 

Date: Mon, 10 Jan 2005 21:25:00 +0000

On 9 Jan 2005 13:39:04 -0800, newcool@gmail.com wrote:

>Hi, I have written a java program where a number has to be tested for
>primality. The number is always smaller then 10^12.
>
>Right now I use the sieve of Eratosthenes with this method:
>
>public boolean IsPrime(long testPrime)
>{
>long test;
>
>test = 2;
>while ( test < (Math.sqrt(testPrime) ) )
>{
>if ( testPrime % test == 0 )
>return false;
>
>if ( test == 2 )
>test++;
>else
>test += 2;
>
>}
>return true;
>}
>
>I have tried using the BigInteger.isProbablePrime method, but that even
>takes longer. I am looking for another method to test for primality
>for integers less then 10^12.
>
>Thanks for any help

I am not sure what you mean about the Sieve of Eratosthenes. Your
code does not use the Sieve, it uses trial division. The Sieve is
useful for generating long lists of primes very quickly rather than
for directly testing individual numbers. The basic algorithm for the
Sieve is:

sieve(bit_array) // Parameter passed by reference
begin
  set all bits in bit_array to 1
  clear bit_array[0]
  clear bit_array[1]
  for i = 2 to sqrt(bit_array.size())
    if bit_array[i] == 1
      for j = i * i to bit_array.size() step i
        clear bit_array[j]
      end for
    end if
  end for
end sieve

The result is a bit array where each bit position has 0 for a
composite and 1 for a prime. For numbers less than the size of
bit_array isPrime becomes:

    boolean isPrime(int n) { return (1 == bit_array[n]); }

which is extremely fast.

Looking at your code you have one potential error, you need to compare
less than *or equal to* sqrt(testPrime) to correctly classify
composite numbers which are the square of a prime number, like 49 =
7^2.

Depending on how well your compiler is optimising you might want to
pull the square root function outside the loop so it is only evaluated
once; square roots are costly. Also you can save evaluating "if (test
== 2)" by dealing with even numbers right at the start. Inside the
loop this test is only useful once so it is best to move it outside.
This gives:

// In C++
bool IsPrime(long testPrime)
{
    if (0 == (testPrime % 2)) { return (2 == testPrime); }

    long test = 3;
    long limit = (long)std::sqrt(testPrime);
    while ( test <= limit ) // Use <=, not <
    {
        if ( testPrime % test == 0L )
            return false;
        test += 2L;
    }
    return true;
}

If you do want to use the Sieve in the context of your code you could
do an initial Sieve to set up a static bit array up to 10^6, which
covers the range needed for your test variable. Numbers less than
10^6 could be done directly as a lookup in the bit array. Trial
division would then only be needed for anything larger than 10^6. Use
the bit array to write a function

    long next_prime(long num)

to return the next prime after a given number. This would replace
your line "test += 2;" and means that you will avoid dividing by
composite numbers, which is a waste of time.

An alternative way to avoid some division by composite numbers without
going to the trouble of doing a Sieve is to start from 5 and add two
and four alternately. This skips over all multiples of three at the
cost of an extra subtraction inside the loop. The trial division by
three needs to be handled explicitly before entering the loop.

// In C++
bool IsPrime(long testPrime)
{
    if (0 == (testPrime % 2)) { return (2 == testPrime); }
    if (0 == (testPrime % 3)) { return (3 == testPrime); }

    long test = 5;
    long increment = 2;
    long limit = (long)std::sqrt(testPrime);
    while ( test <= limit ) // Use <=, not <
    {
        if ( testPrime % test == 0L )
            return false;
        test += increment;
        increment = 6L - increment; // Add 2 and 4 alternately
    }
    return true;
}

This method is better when you only have a few numbers to test and you
do not want to incur the initial cost of doing a Sieve. If you have a
lot of numbers to test then the Sieve will be faster overall since the
one-off cost of the Sieve is spread out among all the numbers tested
and each individual test will run faster.

rossum 

--
The ultimate truth is that there is no Ultimate Truth

Relevant Pages