[lilVaratep]

I have written a method that checks whether a number is prime. Numbers like 22,33,44,55 come up as true when it shouldn't be.

public static boolean isPrime(int number) {
		int i;
		for (i = 2; i <= number; i++) {
			if(number % 1 == 0)
			break;
		}
		if(number == i) {
			return false;
		} else
			return true;

	}

[macosxnerd101]

Look here if(number % 1 == 0). Every number is evenly divisible by 1. Really, you just have to iterate from 2-sqrt(n). If the number, and then skip the evens after 2.

double root = Math.sqrt(n);
for(int i = 3; i < root; i += 2){
    //check to see if n is evenly divisible by i
}

This post has been edited by macosxnerd101: 29 November 2011 - 12:51 PM
Reason for edit:: Set i = 3, not 2

[lilVaratep]

What would i += 2 do, if n % i == 0? If n is not evenly divisible by i, which is 2, wouldn't adding 2 do nothing?

[macosxnerd101]

Since we know that all the even numbers after 2 aren't prime, there is no need to check if n%4 == 0, or n%6 == 0. Checking if n%2 == 0 is sufficient. Which is why we add 2 to i, so to skip the evens. My bad though on setting i = 2 initially. Setting i = 3 initially is the better call. Sorry about that!

[SwiftStriker00]

Well you should probably start your for loop i=3, then increment i+=2. That way you get odd numbers after 2

[lilVaratep]

Here is what I have, and I believe it works:

public static boolean isPrime(int number) {
		int i;
		double root = Math.sqrt(number);
		for (i = 3; i < root; i += 2) {
			if(number % i == 0) {
				return false;
			}
		}
		return true;
	}

Also, I noticed that if I add an else return true after the if statement, I get a compile error: missing return statement. I was wondering why I can't do it this way:

public static boolean isPrime(int number) {
		int i;
		double root = Math.sqrt(number);
		for (i = 3; i < root; i += 2) {
			if(number % i == 0) {
				return false;
			} else
				return true;
		}
	}

[macosxnerd101]

You get that error b/c your for loop may not execute (at least as the compiler sees it, even if it isn't logically the case), so a return statement may not be executed even though one is expected. So you must have a return statement outside of your loop.

[lilVaratep]

Thank you guys =].

[Sheph]

It's possible your for loop never starts, if say the square root of your number is less than 3.

[macosxnerd101]

Glad we could help!

[lilVaratep]

I just realized - 22 shows up as a prime. Is there a loophole, maybe?

[smohd]

If we see the updated code will be useful.
But if a number is even, you dont even need to check for anything, just return not prime, unless less if two.

[lilVaratep]

The updated code is above, or here:

public static boolean isPrime(int number) {
		int i;
		double root = Math.sqrt(number);
		for (i = 3; i < root; i += 2) {
			if(number % i == 0) {
				return false;
			}
		}
		return true;
	}

[smohd]

First check if a number is even or not, if even, then return false(except for two):

//first in the method
if (number%2 == 0 && number > 2)
   return false;
//then you can continue with other issues

And dont forget that 1 is not prime(take care of that also)

[lilVaratep]

smohd, on 29 November 2011 - 04:05 PM, said:

First check if a number is even or not, if even, then return false(except for two):

//first in the method
if (number%2 == 0 && number > 2)
   return false;
//then you can continue with other issues

And dont forget that 1 is not prime(take care of that also)

This also did not work for me, so I tried this and it worked:

public static boolean isPrime(int number) {
		for(int i = 2; i <= number / 2; i++) {
			if(number % i == 0) {
				return false;
			}
		}
		return true;
	}