What's wrong with this code? Prime Numbers

Question

I know this is not the best nor the most efficient way to find prime numbers; However, I can't seem to find the reason why 169 counts as a prime number (for smaller numbers it works OK as far as I'm concerned).

public static int checkPrime(int num, int i)
{
    if (i == num)
        return 1;

    else
    {
        if (num % i == 0)
            return 0;
        else
            checkPrime(num, i+1);

    }

    return 1;
}

Main Class:

        System.out.println("Type a number");
        number = reader.nextInt();

        if ((number % 10) % 2 == 0)
            result = 0;

        else
            result = checkPrime(number, 2);

        if (result == 1 || number == 2)
            System.out.println(number + " is a prime number");
        else
            System.out.println(number + " is NOT a prime number");

If you are checking is some number a prime number, why are you checking others too? Just say `if(number % divider == 0) ...`. — MikkoP, May 12 '12 at 10:45
You should run this in the debugger to discover where its behaviour diverges from what you expected. — Oliver Charlesworth, May 12 '12 at 10:46
Also, I believe you may also change to `if (i*i >= num) return 1` since you do not need to check all divisors to be sure it is a prime, but only from 2 up to the square root of num. See [Primality Test](http://en.wikipedia.org/wiki/Primality_test). This would resolve the problem in less recursive cycles. — Edwin Dalorzo, May 12 '12 at 11:01
If you are looking for a better way of checking primality, take a look at [this question](http://stackoverflow.com/q/2385909/335858). — Sergey Kalinichenko, May 12 '12 at 11:03

score 6 · Accepted Answer · edited May 16 '12 at 05:59

Replacing int by boolean for better expressiveness, and returning the value of the recursive call, your method looks like this:

public static boolean checkPrime(int num, int i)
{
    if (i == num)
        return true;    
    else
    {
        if (num % i == 0)
            return false;
        else
            return checkPrime(num, i+1);
    }
}

It still doesn't work for num < 2, it'll run until i overflows. So as your main prime checking function you can write something like:

public static boolean checkPrime(int num)
{
   if(num<2)
     return false;
   else
     return checkPrime(num, 2);
}

btw (number % 10) % 2 is equivalent to number % 2.

What's wrong with this code? Prime Numbers

1 Answers1