# square root and prime numbers

• 09-19-2010, 02:59 AM
roud9
square root and prime numbers
Hello

It is the first time that I post on this site, so I do not know if it really
good category. I try to write a small java program that determines if a number is
prime or not, it looks like this:

if (nombreEntré % 2 != 0)
System.out.println(nombreEntré +" est un nombre premier"); // prime
else if(nombreEntré % 2 == 0 && nombreEntré != 2)
System.out.println(nombreEntré +" n'est pas un nombre premier"); // not prime

but if I write 51 or 25 (which are not prime number) it said me prime because it is odd. My question is what way should we change the program to detect odd numbers compounds as non-prime?

And I try to express the square root of a number, but Math.sqrt () instead of loop with if ... else or while statement. is there a way?

• 09-19-2010, 03:50 AM
Zack
For the square rooting, and you want to use a loop, you could check every number up to the number to see if it's a square root. This isn't a very good method though; Math.sqrt() is much better.
Code:

```Example: for (i = 0; i < num; i++) {     if (i*i == num) return i; // If some number times itself is our number, return that. } // Note that this method will only find square roots of squares, such as 49, 64, etc.```
To detect a prime number, you need to run through every number up to half of the number, and see if they're factors of each other. If none match, it's prime.
Code:

```Example (informal psuedocode): for (i from 0 to num) {     if (num % i == 0) { // % checks the remainder of a division; if it's 0, then it's evenly divisible         // num is evenly divisible by i, so this number cannot be prime     } }```

Hope that helps a bit.
• 09-19-2010, 08:17 AM
JosAH
Quote:

Originally Posted by Zack
To detect a prime number, you need to run through every number up to half of the number, and see if they're factors of each other. If none match, it's prime.

Nope, for a check for primality for a number n, you need to run through every number up to sqrt(n). A bit of trickery in the for-loop code itself can avoid the Math.sqrt(n) call completely:

Code:

```for (int i= 2; i*i <= n; i++)   ...```
A bit more trickery shows that all prime numbers (except 2 and 3) are multiples of 6 +- 1. Most people ignore this little fact.

kind regards,

Jos
• 09-19-2010, 11:31 AM
dinosoep
Quote:

Originally Posted by JosAH
A bit more trickery shows that all prime numbers (except 2 and 3) are multiples of 6 +- 1. Most people ignore this little fact.

kind regards,

Jos

wow, thanks. I didn't even knew that :)
• 09-19-2010, 12:38 PM
JosAH
Quote:

Originally Posted by dinosoep
wow, thanks. I didn't even knew that :)

Yup, it complicates the preamble of a prime testing method a bit but it speeds up the loop:

Code:

```boolean isPrime(int n) {   if (n < 2) return false; // one isn't prime by definition   if (n == 2 || n == 3) return true; // filter out the simple cases   if (n%2 == 0 || n%3 == 0) return false; // those can't be prime   int inc= 2;   for (int i= 5; i*i <= n; i+= inc, inc= 6-inc) {       // test if n can be divided by i; if so n is not prime   }   return true; }```
Note the fiddling with the value of inc; it alternates values 2, 4, 2, 4 etc. so, starting with the value 5, only values that are a multiple of 6 +- 1 are checked.

kind regards,

Jos
• 09-20-2010, 11:03 PM
roud9
Thanks for your reply I find what I want and how to do it. But I want a while loop instead of for loop

Code:

```for (int k = 0; k < 20; k++)             racineCarrée = (racineCarrée + (nombreEntré / racineCarrée)) / 2;                 if (racineCarrée * racineCarrée != nombreEntré)         {             System.out.println("La racine entière approximative est " + racineCarrée);             racineApprox ++;             compteurRacines ++;         }         else         {             System.out.println("La racine entière exacte est " + racineCarrée);             racineExacte ++;             compteurRacines++;         }```
Thanks again for help me
• 09-20-2010, 11:37 PM
Zack
A for loop is a hybrid construct of a while loop:
Code:

```a; while (b) {     d;     c; }```
Code:

```for (a; b; c) {     d; }```
Those two are identical in what they accomplish. This should help you convert your for to a while loop.
• 09-20-2010, 11:59 PM
roud9
Thanks :)

when I write 15, the square root give me 4 instead of 3

Code:

```racineCarrée = nombreEntré / 2;         int k = 0;         while (k > 20)         {             k ++;         }             racineCarrée = (racineCarrée + (nombreEntré / racineCarrée)) / 2;                 if (racineCarrée * racineCarrée != nombreEntré)         {             System.out.println("La racine entière approximative est " + racineCarrée);             racineApprox ++;             compteurRacines ++;         }         else         {             System.out.println("La racine entière exacte est " + racineCarrée);             racineExacte ++;             compteurRacines++;         }```
• 09-21-2010, 12:22 AM
collin389
you need this:
Code:

`racineCarrée = (racineCarrée + (nombreEntré / racineCarrée)) / 2;`
• 09-21-2010, 12:28 AM
roud9
The same thing give me 7 now :confused:
• 09-21-2010, 12:30 AM
collin389
oh, your while loop whould be:
Code:

```k=0; while(k<20) { racineCarrée = (racineCarrée + (nombreEntré / racineCarrée)) / 2; k++; }```
also, keep in mind that "racineCarrée" needs to be a double for it to work properly
• 09-21-2010, 12:33 AM
roud9
Omg thanks a lot I put racineCarrée = (racineCarrée + (nombreEntré / racineCarrée)) / 2; after k ++;
• 09-21-2010, 08:27 AM
JosAH
Quote:

Originally Posted by roud9
Omg thanks a lot I put racineCarrée = (racineCarrée + (nombreEntré / racineCarrée)) / 2; after k ++;

Why do you need to calculate the approximation of the square root? You don't need it at all (see the code snippet in my previous reply).

kind regards,

Jos
• 09-21-2010, 03:50 PM
roud9
because I don't need the decimal part
• 09-21-2010, 03:59 PM
JosAH
Quote:

Originally Posted by roud9
because I don't need the decimal part

But in your search for prime numbers you don't need an integer approximation either ...

kind regards,

Jos
• 09-21-2010, 04:01 PM
roud9
Okay thanks I will check this
• 09-22-2010, 03:20 PM
JosAH
Did anyone actually read my reply #5 or is it completely ignored again? You don't need to explicitly calculate the square root of anything?

kind regards,

Jos