[Solved] prime checking c++ function outputs numbers that aren’t prime

Question

An extra speed up to solution of Aconcagua can be obtained when you realize that all primes bigger than 3 can be written as 6n+1 or 6n+5 for natural n. Or even further, all primes bigger than 5 can be written as 30n+m, with m in {1,7,11,13,17,19,23,29}. This is what is called Wheel factorization.

This is simply understood as:

Wheel factorization of 2 (cfr. Aconcagua): If n is not divisible by 2, then n is not divisible by any multiple of 2
Wheel factorization of 6=2×3: If n is not divisible by 2, then n is not divisible by any multiple of 2 and if n is not divisible by 3, then n is not divisible by any multiple of 3.
Wheel factorization of 30=2x3x5: See above

So implementing the Wheel factorization of 6, quickly gives:

if (num == 1)     return false;
if (num  < 4)     return true;
if (num % 2 == 0) return false;
if (num % 3 == 0) return false;
int w = 5;
while (w*w <= num)
{
    if(num % (w-2) == 0) return false;
    if(num % w     == 0) return false;
    w += 6;
}
return true;

This algorithm should run at 2/3rd the speed to the solution of Aconcagua.

remark: the wheel factorization of 30 would only give a minor speedup as it only eliminates the sequence 30n+25 which is also covered by the wheel factorization of 6 as 6*(5*n + 4)+1.

remark: this still tests numbers which should not be tested, example (w=25 while we already know that w-2=5 is tested, ditto for 35,49,…)

If you want to go a bit more robust and use a bit of memory, you might be interested in the Sieve of Eratosthenes.

Other useful information can be found here : primes

Accepted Answer