views:

196

answers:

8

I'm trying to make a method that will tell me weather or not it is true or false that a number is prime. here's the code:

class prime
{

    public static boolean prime (int a, int b) 
    { 
        if (a == 0) 
        {
            return false; 
        }
        else if (a%(b-1) == 0) 
        {
            return false; 
        }
        else if (b>1) 
        {
            prime (a, b-1) ;
        }
        else
        {
            return true; 
        }

    }

    public static void main (String[] arg) 
    {
        System.out.println (prime (45, 45)) ; 
    }
}

when i try to compile this i get this error message:

prime.java:23: missing return statement
    }
    ^
1 error

I could be misinterpreting what the error message is saying but it seems to me that there isn't a missing return statement since i have a return statement for every possible set of conditions. if a is 0 then it returns false, if it isn't then it checks to see if a is dividable by b if it is then it returns if not then if b is greater than 1 it starts over again. if b isn't greater than 1 it also returns.

  • Also it seems a bit messy to have to make this method take two ints that are the same int.

  • What is wrong with my syntax/ why am i getting the error message? Is there a way to make it so that the method that i use in main only has to take one int (perhaps another method splits that int into two clones that are then passed to public static boolean primeproper?

  • or is there a more effective way of going about this that i'm missing entirely?

+4  A: 

If b is larger than 1, your function won't return anything.

May it be return prime (a, b-1) ; ?

henchman
That is, you must use `return prime (a, b-1) ;` instead of just `prime (a, b-1) ;`
David
but if b>1 then it will run through prime again until it isn't the case that b>1.
David
also that doens't make it work right. if i do that then it says that 7 isn't prime. 7 is prime.
David
Tom put it well in his answer. You still need to explicitly return the result of the call to the prime(...) method. **Every** invocation of the method must reach a return statement, not just reach one eventually.
David
(This is confusing. I am David from comment #1 and #4, not the asker). If the logic is wrong that is a different problem. To fix your syntax problem you just need to put `return` in front of the call to `prime(...)`
David
i know the logic being wrong is a diferent problem but i was wondering if you had any idea what to do about it?
David
Ah I see. I think paxdiablo's answer has some good info on ways to improve your algorithm.
David
it does but it doesn't explain why its telling me that 7 is prime which i would really like to know so that i know what i did wrong.
David
+5  A: 

You seem to be under the impression that because the recursion will eventually find a base-case which will hit a return statement, then that return will bubble up through all of the recursive calls. That's not true. Each recursive call must pass out the result like this:

return prime(a, b - 1);
tom
ok but when i make that change it thinks 7 isn't prime. whats going wrong?
David
David: when b is 2, the expression `a%(b-1) == 0` is true for all a, so it always ends up returning false.
Chris Dodd
+3  A: 
erickson
don't i need to test every factor from 2-(n-1)? [n-1 not n, since if it tested dividing by n it would think that the number wasn't prime because it%n would =0.
David
also what does it mean to say that the method is private like that? what does that do?
David
WTF? Now I go to go and look up "didactic" :-)
paxdiablo
well that doesn't answer the question very well.
David
+6  A: 

In your prime function, there are four possible code paths, one of which doesn't return anything. That is what the error message is complaining about. You need to replace:

prime (a, b-1) ;

with:

return prime (a, b-1) ;

in the else if (b>1) case.

Having said that, this is actually not a good way to calculate if a number is prime. The problem is that every recursive call allocates a stack frame and you'll get into serious stack overflow problems if you're trying to work out whether 99,999,999 is a prime number?

Recursion is a very nice tool for a certain subset of problems but you need to be aware of the stack depth. As to more efficient solutions, the are many tests you can carry out to determine a number is not prime, then only check the others with a brute force test.

One thing you should be aware of is to check divisibility against smaller numbers first since this will reduce your search scope quicker. And don't use divide where multiply will do, multiplication is typically faster (though not always).

And some possibly sneaky tricks along the lines of:

  • every number other than 2 that ends in 2, 4, 6, 8 or 0 is non-prime.
  • every number other than 5 that ends in 5 is non-prime. Those two rules alone will reduce your search space by 60%. Assuming you get your test number as a string, it's a simple matter to test the last digit of that string even before converting to an integral type.

There are some more complex rules for divisibility checks. If you take a multiple of 9 and sum all the digits to get a new number, then do it again to that number, then keep going until you have a single digit, you'll find that it's always 9.

That will give you another 10% reduction in search space albeit with a more time-expensive check. Keep in mind that these checks are only advantageous for really large numbers. The advantages are not so great for, say, 32-bit integers since a pre-calculated bitmap would be much more efficient there (see below).

For a simplistic start, I would use the following iterative solution:

public static boolean prime (int num) {
    int t = 2;
    while (t * t <= num) {
        if ((num % t) == 0) {
            return false;
        }
        t++;
    }
    return true;
}

If you want real speed in your code, don't calculate it each time at all. Calculate it once to create a bit array (one of the sieve methods will do it) of all primes across the range you're interested in, then simply check your values against that bit array.

If you don't even want the cost of calculating the array every time your program starts, do it once and save the bit array to a disk file, loading it as your program starts.

I actually have a list of the first 100 million primes in a file and it's easier and faster for me to use grep to find if a number is prime, than to run some code to calculate it :-)


As to why your algorithm (fixed with a return statement) insists that 7 is not prime, it will insist that every number is non-prime (haven't checked with negative numbers, I'm pretty sure they would cause some serious problems - your first check should probably be if (a < 1) ...).

Let's examine what happens when you call prime(3,3).

First time through, it hits the third condition so calls prime(3,2).

Then it hits the second condition since 3 % (2-1) == 0 is true (N % 1 is always 0).

So it returns false. This could probably be fixed by changing the third condition to else if (b>2) although I haven't tested that thoroughly since I don't think a recursive solution is a good idea anyway.


The following complete code snippet will do what you need although I appreciate your curiosity in wanting to know what you did wrong. That's the mark of someone who's actually going to end up a good code cutter.

public class prime
{
    public static boolean isPrime (int num) {
        int t = 2;
        while (t * t <= num) {
            if ((num % t) == 0) {
                return false;
            }
            t++;
        }
        return true;
    }


    public static void main (String[] arg) 
    {
        System.out.println (isPrime (7)) ; 
    }
}
paxdiablo
well whats a better way?
David
what does while mean? and what does t++ mean? Also shouldn't num%t alwayse = 0 since num/t=t?
David
@David, 'while' will continue the loop as long as the condition is true (until t is greater than the square root of num, where you're guaranteed that num cannot be an exact multiple of t). t++ adds 1 to t. And num%t will only be 0 if num is an exact multiple of t, i.e., the number is not prime.
paxdiablo
A: 

Your recursive method must return a value so it can unroll.

    public static boolean prime (int a, int b) 
{
    if (a == 0) 
    {
        return false; 
    }
    else if (a%(b-1) == 0) 
    {
        return false; 
    }
    else if (b>1) 
    {
        return prime (a, b-1) ;
    }
    else
    {
        return true; 
    }

}

I might write it a different way, but that is the reason that you are not able to compile the code.

Rob Goodwin
what does unroll mean?
David
@David he means when the recursion comes to a stopping condition, there will be a series of `returns` as the recursed `prime` methods are popped from the stack. He means the return value will propagate back to the original prime() call.
Jonathon
+2  A: 

In answer to why 7 isn't working, pretend you're the computer and work through your logic. Here's what you wrote.

class prime
{

    public static boolean prime (int a, int b) 
    { 
        if (a == 0) 
        {
            return false; 
        }
        else if (a%(b-1) == 0) 
        {
            return false; 
        }
        else if (b>1) 
        {
            // Have to add the return statement
            // here as others have pointed out!
            return prime(a, b-1);
        }
        else
        {
            return true; 
        }

    }

    public static void main (String[] arg) 
    {
        System.out.println (prime (45, 45)) ; 
    }
}

So let's start with 7.

if(7 == 0) // not true, don't enter this block
else if(7 % 6 == 0) // not true
else if(7 > 1) // true, call prime(7, 6)

if(7 == 0) // not true, don't enter this block
else if(7 % 5 == 0) // not true
else if(6 > 1) // true, call prime(7, 5)

if(7 == 0) // not true, don't enter this block
else if(7 % 4 == 0) // not true
else if(5 > 1) // true, call prime(7, 4)

... keep going down to calling prime(7, 2)

if(7 == 0) // not true, don't enter this block

else if(7 % 1 == 0) true, return false

When you get down to calling prime(n, 2), it will always return false because you have a logic error.

Jonathon
A: 

I think the original question was answered already - you need to insert return in the body of else if (b>1) - I just wanted to point out that your code still will crash when given 1 as the value for b, throwing an ArithmeticException since a%(b-1) will be evaluated to a%0, causing a division by zero.

You can avoid this by making the first if-statement if (a == 0 || b == 1) {} This won't improve the way the program finds primes, it just makes sure there is one less way to crash it.

A: 

Similar to @paxdiblo's answer, but slightly more efficient.

public static boolean isPrime(int num) {
    if (num <= 1 || (num & 1) == 0) return false;
    for (int t = 3; t * t <= num; t += 2)
        if (num % t == 0)
            return false;
    return true;
}

Once it is determined that the number is not even, all the even numbers can be skipped. This will halve the numbers which need to be checked.

Peter Lawrey