Checking prime numbers

  • (2 Pages)
  • +
  • 1
  • 2

15 Replies - 546 Views - Last Post: 29 November 2011 - 10:17 PM Rate Topic: -----

#1 lilVaratep  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 22
  • View blog
  • Posts: 218
  • 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  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10773
  • View blog
  • Posts: 40,122
  • 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

Was This Post Helpful? 0
  • +
  • -

#3 lilVaratep  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 22
  • View blog
  • Posts: 218
  • 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?
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10773
  • View blog
  • Posts: 40,122
  • 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!
Was This Post Helpful? 1
  • +
  • -

#5 SwiftStriker00  Icon User is offline

  • No idea why my code works
  • member icon

Reputation: 433
  • View blog
  • Posts: 1,599
  • 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
Was This Post Helpful? 1
  • +
  • -

#6 lilVaratep  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 22
  • View blog
  • Posts: 218
  • 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;
		}
	}

Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10773
  • View blog
  • Posts: 40,122
  • 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.
Was This Post Helpful? 2
  • +
  • -

#8 lilVaratep  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 22
  • View blog
  • Posts: 218
  • Joined: 09-October 11

Re: Checking prime numbers

Posted 29 November 2011 - 01:02 PM

Thank you guys =].
Was This Post Helpful? 0
  • +
  • -

#9 Sheph  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 432
  • View blog
  • Posts: 1,020
  • 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.
Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10773
  • View blog
  • Posts: 40,122
  • Joined: 27-December 08

Re: Checking prime numbers

Posted 29 November 2011 - 01:03 PM

Glad we could help! :)
Was This Post Helpful? 0
  • +
  • -

#11 lilVaratep  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 22
  • View blog
  • Posts: 218
  • 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?
Was This Post Helpful? 0
  • +
  • -

#12 smohd  Icon User is offline

  • Critical Section
  • member icon


Reputation: 1820
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#13 lilVaratep  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 22
  • View blog
  • Posts: 218
  • 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;
	}

Was This Post Helpful? 0
  • +
  • -

#14 smohd  Icon User is offline

  • Critical Section
  • member icon


Reputation: 1820
  • View blog
  • 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)
Was This Post Helpful? 0
  • +
  • -

#15 lilVaratep  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 22
  • View blog
  • Posts: 218
  • Joined: 09-October 11

Re: Checking prime numbers

Posted 29 November 2011 - 05:17 PM

View Postsmohd, 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;
	}

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2