prime checking c++ function outputs numbers that aren't prime

Question

I am making a C++ program that allows you to input a number and checks if it is prime. But it says that numbers like 9, 15, and 21 are prime. Can I have some help? It is quite confusing. Here is my function that checks if it is prime:

bool isPrime(int num) {

    int w = 2;

    while (w <= num) {

        if (w % num == 0) {
                return false;
        }
        else if (w < num){
            w = w + 1;
        }

        if (w == num) {
            w = 0;
            return true; 
        }
    }
}

Answer 1

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=2x3: 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