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; }

## 15 Replies - 730 Views - Last Post: 29 November 2011 - 10:17 PM

### #1

# Checking prime numbers

Posted 29 November 2011 - 12:30 PM

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.

##
**Replies To:** Checking prime numbers

### #2

## Re: Checking prime numbers

Posted 29 November 2011 - 12:32 PM

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

### #3

## Re: Checking prime numbers

Posted 29 November 2011 - 12:49 PM

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?

### #4

## Re: Checking prime numbers

Posted 29 November 2011 - 12:52 PM

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!

### #5

## Re: Checking prime numbers

Posted 29 November 2011 - 12:52 PM

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

### #6

## Re: Checking prime numbers

Posted 29 November 2011 - 12:59 PM

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

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; } } 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; } }

### #7

## Re: Checking prime numbers

Posted 29 November 2011 - 01:01 PM

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.

### #9

## Re: Checking prime numbers

Posted 29 November 2011 - 01:02 PM

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

### #11

## Re: Checking prime numbers

Posted 29 November 2011 - 04:35 PM

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

### #12

## Re: Checking prime numbers

Posted 29 November 2011 - 04:48 PM

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.

But if a number is even, you dont even need to check for anything, just return not prime, unless less if two.

### #13

## Re: Checking prime numbers

Posted 29 November 2011 - 04:54 PM

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; }

### #14

## Re: Checking prime numbers

Posted 29 November 2011 - 05:05 PM

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

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

//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)

### #15

## Re: Checking prime numbers

Posted 29 November 2011 - 05:17 PM

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):

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

//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; }