# Thread: square root and prime numbers

1. Member Join Date
Sep 2010
Posts
20
Rep Power
0

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

Last edited by roud9; 09-19-2010 at 03:02 AM.  Reply With Quote

2. ## 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.
Java 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.
Java 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.  Reply With Quote

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

Java 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  Reply With Quote

4. Senior Member Join Date
Nov 2009
Posts
150
Rep Power
11

##  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 :)  Reply With Quote

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

Java 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
Last edited by JosAH; 09-19-2010 at 02:00 PM.  Reply With Quote

6. Member Join Date
Sep 2010
Posts
20
Rep Power
0

## Thanks for your reply I find what I want and how to do it. But I want a while loop instead of for loop

Java 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  Reply With Quote

7. ## A for loop is a hybrid construct of a while loop:
Java Code:
```a;
while (b) {
d;
c;
}```
Java 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.  Reply With Quote

8. Member Join Date
Sep 2010
Posts
20
Rep Power
0

## Thanks :)

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

Java 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++;
}```  Reply With Quote

9. Senior Member Join Date
Nov 2009
Posts
236
Rep Power
11

## you need this:
Java Code:
`racineCarrée = (racineCarrée + (nombreEntré / racineCarrée)) / 2;`  Reply With Quote

10. Member Join Date
Sep 2010
Posts
20
Rep Power
0

## The same thing give me 7 now :confused:  Reply With Quote

11. Senior Member Join Date
Nov 2009
Posts
236
Rep Power
11

## oh, your while loop whould be:
Java 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  Reply With Quote

12. Member Join Date
Sep 2010
Posts
20
Rep Power
0

## Omg thanks a lot I put racineCarrée = (racineCarrée + (nombreEntré / racineCarrée)) / 2; after k ++;  Reply With Quote

13. ##  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  Reply With Quote

14. Member Join Date
Sep 2010
Posts
20
Rep Power
0

## because I don't need the decimal part  Reply With Quote

15. ##  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  Reply With Quote

16. Member Join Date
Sep 2010
Posts
20
Rep Power
0

## Okay thanks I will check this  Reply With Quote

17. ## 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  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•