Results 1 to 17 of 17
  1. #1
    roud9 is offline Member
    Join Date
    Sep 2010
    Posts
    20
    Rep Power
    0

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

    Sorry for my bad english

    Thank you in advance
    Last edited by roud9; 09-19-2010 at 03:02 AM.

  2. #2
    Zack's Avatar
    Zack is offline Senior Member
    Join Date
    Jun 2010
    Location
    Destiny Islands
    Posts
    692
    Rep Power
    5

    Default

    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. #3
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,526
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Zack View Post
    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. #4
    dinosoep is offline Senior Member
    Join Date
    Nov 2009
    Posts
    150
    Rep Power
    5

    Default

    Quote Originally Posted by JosAH View Post
    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. #5
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,526
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by dinosoep View Post
    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. #6
    roud9 is offline Member
    Join Date
    Sep 2010
    Posts
    20
    Rep Power
    0

    Default

    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. #7
    Zack's Avatar
    Zack is offline Senior Member
    Join Date
    Jun 2010
    Location
    Destiny Islands
    Posts
    692
    Rep Power
    5

    Default

    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. #8
    roud9 is offline Member
    Join Date
    Sep 2010
    Posts
    20
    Rep Power
    0

    Default

    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. #9
    collin389 is offline Senior Member
    Join Date
    Nov 2009
    Posts
    235
    Rep Power
    5

    Default

    you need this:
    Java Code:
    racineCarrée = (racineCarrée + (nombreEntré / racineCarrée)) / 2;
    inside your while loop.

  10. #10
    roud9 is offline Member
    Join Date
    Sep 2010
    Posts
    20
    Rep Power
    0

    Default

    The same thing give me 7 now :confused:

  11. #11
    collin389 is offline Senior Member
    Join Date
    Nov 2009
    Posts
    235
    Rep Power
    5

    Default

    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. #12
    roud9 is offline Member
    Join Date
    Sep 2010
    Posts
    20
    Rep Power
    0

    Default

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

  13. #13
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,526
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by roud9 View Post
    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. #14
    roud9 is offline Member
    Join Date
    Sep 2010
    Posts
    20
    Rep Power
    0

    Default

    because I don't need the decimal part

  15. #15
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,526
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by roud9 View Post
    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. #16
    roud9 is offline Member
    Join Date
    Sep 2010
    Posts
    20
    Rep Power
    0

    Default

    Okay thanks I will check this

  17. #17
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,526
    Blog Entries
    7
    Rep Power
    20

    Default

    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

Similar Threads

  1. Prime Number - System print all the prime numbers ...
    By pinkdreammsss in forum New To Java
    Replies: 20
    Last Post: 04-26-2009, 01:50 AM
  2. Simple square root problem!
    By nortski in forum New To Java
    Replies: 7
    Last Post: 04-01-2009, 02:11 PM
  3. Creating a New Method for Square Root Loop
    By SapphireSpark in forum New To Java
    Replies: 14
    Last Post: 02-25-2009, 01:21 PM
  4. Prime numbers
    By tercius in forum New To Java
    Replies: 3
    Last Post: 05-04-2008, 06:05 AM
  5. Prime numbers
    By gapper in forum New To Java
    Replies: 3
    Last Post: 02-07-2008, 10:09 AM

Posting Permissions

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