This discussion is archived
1 2 Previous Next 23 Replies Latest reply: Nov 6, 2010 4:38 PM by 800147

# Finding a prime number

Currently Being Moderated
Hi,

I am supposed to make a program that displays a prime number in the range 1 to number.

I made it for the range 3 to number.
``````static void prime ( int number ){

for(int i = 3; i <= number; i++){
int r = 0;
for( int j = 2; j <= i - 1; j++){
r = i % j;
if( r == 0 ) {
break;
}
else
r = i % j;
}
if( r != 0 )
System.out.println(i + " is prime");

}
}``````
Any ideas how to incorporate values 1 and 2?

• ###### 1. Re: Finding a prime number
Currently Being Moderated
Since 1 is not prime and 2 is, you could just cheat and have two separate print statements for them before going into the loop for the rest of the numbers.
• ###### 2. Re: Finding a prime number
Currently Being Moderated
Pinto wrote:
Since 1 is not prime and 2 is, you could just cheat and have two separate print statements for them before going into the loop for the rest of the numbers.
:) Absolutely, but I was thinking if I can actually put them in the calculations somehow. But maybe it'll be just easier with the print statements.
• ###### 3. Re: Finding a prime number
Currently Being Moderated
You can definately change your code to handle 2 but 1 is a special case. Even though it doesn't have any divisors it is still not considered prime.
• ###### 4. Re: Finding a prime number
Currently Being Moderated
``j <= i - 1``
You can make it many times as fast by changing that to:
``j*j < i``
Do you understand why?
• ###### 5. Re: Finding a prime number
Currently Being Moderated
EJP wrote:
``j <= i - 1``
You can make it many times as fast by changing that to:
``j*j < i``
Do you understand why?
That fails for 3. Better and more common approach is j less than or equal to square root of i
• ###### 6. Re: Finding a prime number
Currently Being Moderated
Hehe

The square root method also fails for 3 due to how OP has written the code.
• ###### 7. Re: Finding a prime number
Currently Being Moderated
Better and more common approach is j less than or equal to square root of i
Please explain analytically the difference between
``j*j <  i``
and
``j < Math.sqrt(i)``
and please enumerate one or more cases for which they yield different results.
• ###### 8. Re: Finding a prime number
Currently Being Moderated
Yeah yeah yeah

I was momentarily blinded by the fact that it didn't work until I realised it was the algorithm at fault.
• ###### 9. Re: Finding a prime number
Currently Being Moderated
Precisely. I note also that evaluating j*j is several times as fast as evaluating the square root of i.

There is also no point whatsoever in the OP's 'else' block.
• ###### 10. Re: Finding a prime number
Currently Being Moderated
EJP wrote:
``j <= i - 1``
You can make it many times as fast by changing that to:
``j*j < i``
Do you understand why?
• ###### 11. Re: Finding a prime number
Currently Being Moderated
blias wrote:
EJP wrote:
``j <= i - 1``
You can make it many times as fast by changing that to:
``j*j < i``
Do you understand why?
I want to find the factors of 36:
``````   1  2  3  4  6  9  12 18 36
x
36 18 12  9  6  4  3  2 1``````
See how once I hit 6--that is, the square root of 36--everything starts repeating? By the time I hit the sqrt, I have found all the factors. So by the time I hit the sqrt of some number, if I haven't found any factors other than that number and 1, there aren't any, so it's prime.

So, if you want to know if 100,000,007 is prime, would you rather iterate through 100 million values, or 10 thousand?

Edited by: jverd on Nov 5, 2010 11:27 AM
• ###### 12. Re: Finding a prime number
Currently Being Moderated
Thanks for the great explanation, jverd. I understand it.

Since I am still unable to incorporate the algorithm into my code I've decided to try to put your explanation into a code that finds the factors (as first step). Hopefully I'll get better understanding once I get it working.
``````static void factors ( int number ){

StringBuilder sb = new StringBuilder();
StringBuilder sb1 = new StringBuilder();
int r = 0;

for( int i = 1; i < Math.sqrt(number); i++){
if(number % i == 0){
r = number / i;
if( sb.length() != 0 )
sb.insert(sb.length(), " ,");
sb.insert(sb.length(), r);
if( sb1.length() != 0 )
sb1.insert(sb1.length(), " ,");
sb1.insert(sb1.length(), i);
}
}

System.out.println(number + " has factors " + sb + " ," + sb1);

}``````
If I get 36 as an example the program misses the sqrt value itself. I understand it is because
``for( int i = 1; i < Math.sqrt(number); i++)``
but if I change
``i <= Math.sqrt(number; ``
I get the value displayed twice.

Any hints?
• ###### 13. Re: Finding a prime number
Currently Being Moderated
Just wondering what would happen if someone entered a negative number such as -5. Is that considered a prime number? what would your code produce?
• ###### 14. Re: Finding a prime number
Currently Being Moderated
First, rather than
``i < Math.sqrt(number)``
I recommend you follow EJP's suggestion and use
``i * i <= number``
That will be faster, and keep you in the realm of integers. (Though it will mean you'll have a smaller range you can work with before you have to upgrade to long or BigInteger).

As for duplicating the sqrt, I hope you see why it's happening. You're appending both factors, and in the case of the sqrt, both factors are the same. Just add a simple if test for i * i != number or i != r before doing the second append.