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

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.

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

4. Senior Member
Join Date
Nov 2009
Posts
150
Rep Power
8
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 :)

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.

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

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.

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

9. Senior Member
Join Date
Nov 2009
Posts
235
Rep Power
8
you need this:
Java Code:
`racineCarrée = (racineCarrée + (nombreEntré / racineCarrée)) / 2;`

10. Member
Join Date
Sep 2010
Posts
20
Rep Power
0
The same thing give me 7 now :confused:

11. Senior Member
Join Date
Nov 2009
Posts
235
Rep Power
8
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

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

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

14. Member
Join Date
Sep 2010
Posts
20
Rep Power
0
because I don't need the decimal part

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

16. Member
Join Date
Sep 2010
Posts
20
Rep Power
0
Okay thanks I will check this

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

#### Posting Permissions

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