# Checking prime numbers

• (2 Pages)
• 1
• 2

## 15 Replies - 637 Views - Last Post: 29 November 2011 - 10:17 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=257683&amp;s=d1822e03ec989928677af7ec33175aae&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 lilVaratep

• D.I.C Regular

Reputation: 36
• Posts: 285
• Joined: 09-October 11

# 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.

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

}
```

Is This A Good Question/Topic? 0

## Replies To: Checking prime numbers

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11307
• Posts: 42,584
• Joined: 27-December 08

## 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 lilVaratep

• D.I.C Regular

Reputation: 36
• Posts: 285
• Joined: 09-October 11

## 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 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11307
• Posts: 42,584
• Joined: 27-December 08

## 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 SwiftStriker00

• No idea why my code works

Reputation: 438
• Posts: 1,611
• Joined: 25-December 08

## 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 lilVaratep

• D.I.C Regular

Reputation: 36
• Posts: 285
• Joined: 09-October 11

## Re: Checking prime numbers

Posted 29 November 2011 - 12:59 PM

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

### #7 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11307
• Posts: 42,584
• Joined: 27-December 08

## 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.

### #8 lilVaratep

• D.I.C Regular

Reputation: 36
• Posts: 285
• Joined: 09-October 11

## Re: Checking prime numbers

Posted 29 November 2011 - 01:02 PM

Thank you guys =].

### #9 Sheph

• D.I.C Lover

Reputation: 444
• Posts: 1,030
• Joined: 12-October 11

## 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.

### #10 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11307
• Posts: 42,584
• Joined: 27-December 08

## Re: Checking prime numbers

Posted 29 November 2011 - 01:03 PM

### #11 lilVaratep

• D.I.C Regular

Reputation: 36
• Posts: 285
• Joined: 09-October 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 smohd

• Critical Section

Reputation: 1820
• Posts: 4,627
• Joined: 14-March 10

## 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.

### #13 lilVaratep

• D.I.C Regular

Reputation: 36
• Posts: 285
• Joined: 09-October 11

## 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 smohd

• Critical Section

Reputation: 1820
• Posts: 4,627
• Joined: 14-March 10

## 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):
```//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 lilVaratep

• D.I.C Regular

Reputation: 36
• Posts: 285
• Joined: 09-October 11

## 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):
```//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;
}
```