13 Replies Latest reply: Mar 29, 2007 10:49 PM by DrClap RSS

    More prime number crunching. (sum of 2 suqares)

    807606
      Im haiving a problem finding an algorithm or a way to get the last part of my program, the program inters an integer, and checks every prime number up to the input number n, for each prime found, the program decides if it can be written as the sum of two squares.
      So far i have gotten this
      import java.util.Scanner;
      public class Project6 {
           public static void main(String[] args) {
                Scanner input = new Scanner(System.in);
                //Get input from user.
                System.out.println("Enter an integer: ");
                int n = input.nextInt();
                     if (n == 1){
                          System.out.println ("Please input a number greater than 1.");
                     }
                     for(int i = 2; i<=n;i++){
                     sumOfSquares(i);
                     
                     }     
                     
                
           
           }
           public static boolean isPrime(int num){
                for(int div = 2; div <= num/2; div++){
                     if (num % div ==0){
                          return false;
                     }
                }     
                return true;     
                     
                
           }
           public static int nextPrime(int num){
                for (int i = 2; i <= num; i++){
                     if (isPrime(i))
                          return i;
                }
                return 0;
           }
           
            public static void sumOfSquares(int num){
                
                if (isPrime(num)){
                     
                     System.out.println (num+ " = " );
                }
                else{
                     System.out.println (num+ " is not a sum of two squares."
                }
                
           
           }
           
      }
      I have checked the methods and they get the prime numbers fine and whatnot. I am just having trouble comprehinding the how to get the sum of the 2 squares.

      the sample output the teacher gave us is
      enter an integer: 6
      2=1^2 + 1^2
      3 is not a sum of 2 squares
      5 = 1^2 + 2^2

      i know that lets say 13 is the sum of 2^2+3^2
      or 19 is not a sum of 2 squares. Its just the implementation of the algorithm and whatnot that is gettin me stuck. Can any of u lead me onto the algorithm? give ideas or sumthing? i don't want the answer though, just sumthing that makes me go OOOOO I see what to do now.
      any help would be great.
        • 1. Re: More prime number crunching. (sum of 2 suqares)
          569573
          I didn't try this algorithm, but may be give you some idea for reference.
          Let say you input the number n.
          Then find the square up to r
          where 1^2, 2^2 .... r^2 < n
          You have two index, a and b
          starting from a=1, b=r
          1) a^2 + b^2 = n ?
          yes -> you got the answer
          no -> a^2 + b^2 < n
          yes -> a = a + 1;
          no -> b = b - 1;
          (back to step 1, until a>b)
          • 2. Re: More prime number crunching. (sum of 2 suqares)
            807606
            im not quite understanding that statement, but i do notice that all the primes that are not the sum of 2 squares are in some way +4 of the last one,
            3 = no
            7 = no
            11= no
            19= no
            3+4=7
            7+4 = 11
            11+4 +4= 19

            is there anyway to incorperate that into the program?
            • 3. Re: More prime number crunching. (sum of 2 suqares)
              569573
              Do you want to check if the prime number can be formed by two and only two squares or any number ?

              Take n = 29 for example
              Finding r
              1^2, 2^2, 3^2, 4^2, 5^2 < 29 , so r = 5
              a=1, b=r
              a=1, b=5
              1^2 + 5^2 = 29 ?
              no -> 1^2 + 5^2 > 29 ?
              no -> a = a + 1 (i.e. a=2)
              2^2 + 5^2 = 29 ?
              yes

              Take n = 31 for example
              Finding r
              1^2, 2^2, 3^2, 4^2, 5^2 < 29 , so r = 5
              a=1, b=r
              a=1, b=5
              1^2 + 5^2 = 31 ?
              no -> 1^2 + 5^2 > 31 ?
              no -> a = a + 1 (i.e. a=2)
              2^2 + 5^2 = 31 ?
              no -> 2^2 + 5^2 > 31 ?
              no -> a = a + 1 (i.e. a=3)
              3^2 + 5^2 = 31 ?
              no -> 3^2 + 5^2 > 31 ?
              yes b = b + 1 (i.e. b=4)
              3^2 + 4^2 = 31 ?
              no -> 3^2 + 4^2 > 31 ?
              no -> a = a + 1 (i.e. a=4)
              4^2 + 4^2 = 31 ?
              no
              • 4. Re: More prime number crunching. (sum of 2 suqares)
                807606
                Ok what i have now is
                /*daniel rabich
                 * 3/28/07
                 *Project6
                 */
                import java.util.Scanner;
                public class Project6 {
                     public static void main(String[] args) {
                          Scanner input = new Scanner(System.in);
                          //Get input from user.
                          System.out.println("Enter an integer: ");
                          int n = input.nextInt();          
                          int a = 1, r =1;          
                          if (n == 1){
                                    System.out.println ("Please input a number greater than 1.");
                          }
                          for (int i = 2; i <= n; i++)     
                               if (isPrime(i)){
                                    sumOfSquares(i, a, r);                         
                               }               
                     }               
                     public static boolean isPrime(int num){
                          for(int div = 2; div <= num/2; div++){
                               if (num % div ==0){
                                    return false;
                               }
                               if (num % 2 ==0){
                                    return false;
                               }
                          }     
                          return true;          
                     }
                     public static int nextPrime(int num){
                          for (int i = 2; i <= num; i++){
                               if (isPrime(i))
                                    return i;
                          }
                          return 0;
                     }     
                     public static void sumOfSquares(int num, int a, int r){
                           
                          while (Math.pow(r, 2) < num && Math.pow(r, 2) + Math.pow(a, 2) < r){
                               
                               r++;
                          }               
                          while (Math.pow(r, 2) + Math.pow(a, 2) < num){
                               a++;
                          }
                          if (Math.pow(r, 2) + Math.pow(a, 2) == num){
                          System.out.println (num + " = " +a+"^2 + "+r+"^2" );
                           }          
                          else{
                                    System.out.println (num+ " is not the sum of two primes.");     
                          }           
                     }
                }
                its not working how i wanted it, but its getting there, now i have the problem of it doing the 1st numbers ok but then it leaves out stuff like 13, 37, but sum of them in higher numbers are put up there...so idk what the deal is.
                • 5. Re: More prime number crunching. (sum of 2 suqares)
                  DrClap
                  im not quite understanding that statement, but i do
                  notice that all the primes that are not the sum of 2
                  squares are in some way +4 of the last one
                  Well, it's true that if a number is of the form 4n+3 then it can't be a sum of two squares. (That's because a square is either 4m or 4m+1.) So you are observing a real feature of the integers.

                  It's also true that every prime number of the form 4n+1 is a sum of two squares but this is a non-trivial theorem of number theory and I doubt that you should be using it for this project.
                  • 6. Re: More prime number crunching. (sum of 2 suqares)
                    807606
                    /*daniel rabich
                     * 3/28/07
                     *Project6
                     */
                    import java.util.Scanner;
                    public class Project6 {
                         public static void main(String[] args) {
                              Scanner input = new Scanner(System.in);
                              //Get input from user.
                              System.out.println("Enter an integer: ");
                              int n = input.nextInt();          
                              int a = 1, r =1;          
                              if (n == 1){
                                        System.out.println ("Please input a number greater than 1.");
                              }
                              for (int i = 2; i <= n; i++)     
                                   if (isPrime(i)){
                                        sumOfSquares(i, a, r);                         
                                   }               
                         }               
                         public static boolean isPrime(int num){
                              for(int div = 2; div <= num/2; div++){
                                   if (num % div ==0){
                                        return false;
                                   }
                                   if (num % 2 ==0){
                                        return false;
                                   }
                              }     
                              return true;          
                         }
                         public static int nextPrime(int num){
                              for (int i = 2; i <= num; i++){
                                   if (isPrime(i))
                                        return i;
                              }
                              return 0;
                         }     
                         public static void sumOfSquares(int num, int a, int r){
                               
                              while (Math.pow(r, 2) + Math.pow(a, 2)  < num){
                                   r++;
                                   if (Math.pow(r, 2) > num){
                                        r--;
                                        break;
                                   }
                                        
                              
                                   
                                   
                              }               
                              while (Math.pow(r, 2) + Math.pow(a, 2) < num){
                                   a++;
                              }
                              if (Math.pow(r, 2) + Math.pow(a, 2) == num){
                              System.out.println (num + " = " +a+"^2 + "+r+"^2" );
                               }          
                              else{
                                        System.out.println (num+ " is not the sum of two primes.");     
                              }           
                         }
                    }
                    its reformed a little, but it still misses 41, 61 and 89, and some after that "havn't checked larger than n=98, anyone see what im doing wrong?

                    Message was edited by:
                    Sanatarium
                    • 7. Re: More prime number crunching. (sum of 2 suqares)
                      807606
                      By the way, using Math.pow() for squares is CRAZY inefficient.
                      I did a test once and its like 15-20x times slower than just using
                      variable * variable.
                      When doing number crunching like this I would suggest abandoning
                      Math.pow().
                      • 8. Re: More prime number crunching. (sum of 2 suqares)
                        807606
                        /*daniel rabich
                         * 3/28/07
                         *Project6
                         */
                        import java.util.Scanner;
                        public class Project6 {
                             public static void main(String[] args) {
                                  Scanner input = new Scanner(System.in);
                                  //Get input from user.
                                  System.out.println("Enter an integer: ");
                                  int n = input.nextInt();          
                                  int a = 1, r =1;          
                                  if (n == 1){
                                            System.out.println ("Please input a number greater than 1.");
                                  }
                                  for (int i = 2; i <= n; i++)     
                                       if (isPrime(i)){
                                            sumOfSquares(i, a, r);                         
                                       }               
                             }               
                             public static boolean isPrime(int num){
                                  for(int div = 2; div <= num/2; div++){
                                       if (num % div ==0){
                                            return false;
                                       }
                                       if (num % 2 ==0){
                                            return false;
                                       }
                                  }     
                                  return true;          
                             }
                             public static int nextPrime(int num){
                                  for (int i = 2; i <= num; i++){
                                       if (isPrime(i))
                                            return i;
                                  }
                                  return 0;
                             }     
                             public static void sumOfSquares(int num, int a, int r){
                                   
                                  while ((r * r) + (a * a)  < num){
                                       r++;
                                       if (r * r > num){
                                            r--;                    
                                            break;
                                       }               
                                  }               
                                  while (r * r + a * a < num){
                                       a++;
                                       if (r * r + a * a > num){
                                            a--;
                                            break;
                                       }
                                  }
                                  if (r * r + a * a == num){
                                  System.out.println (num + " = " +a+"^2 + "+r+"^2" );
                                   }          
                                  else{
                                            System.out.println (num+ " is not the sum of two primes.");     
                                  }           
                             }
                        }
                        ok i got rid of Math.pow() function, i still can't seem to figure out a way to get 41, 61 and 89, and so on...ne observations on it or hints please?

                        Message was edited by:
                        Sanatarium
                        • 9. Re: More prime number crunching. (sum of 2 suqares)
                          569573
                          What is the purpose of method nextPrime ?

                          I think isPrime and sumOfSquares should be separated, you would find the squares only when you know it is prime.

                          If you want to find out the reason why it is not getting you the pair of sqaures, get some println would really help.
                          • 10. Re: More prime number crunching. (sum of 2 suqares)
                            807606
                            think next prime can be cut out, but is prime and sum of squares are right, my program only finds the sum of squares
                            if (isPrime(i)){
                                                sumOfSquares(i, a, r);                         
                                           }
                            that means if I is prime, then it will put i into the method sum of squares.

                            it works fien up until 41... the print ln is like
                            2+1^2 +1^2
                            3 is not a sum of 2 squares
                            ...ect...
                            37 = 1^2 + 6^2
                            41 is not the sum of two squares.

                            however, 41 is the sum of 4^2 +5^2

                            then it goes back to 43 is not sum of 2 squares, 47 is not , 53 = 2^2 + 7^2
                            ext... until 61 again it says its not when it is 6^2 + 5'2

                            i don't know what i can change or whats happening to make it do that
                            • 11. Re: More prime number crunching. (sum of 2 suqares)
                              569573
                              Why do you need a for-loop for isPrime ?
                              You only need to check the number inputted but not numbers 2,3,... up to this number, right ?

                              Not the best approach but you could initialize a to 1 and r to n.
                              Afterwards, you could pick a better number for r starting.
                              • 12. Re: More prime number crunching. (sum of 2 suqares)
                                569573
                                and for the while loop used for finding the sum of squares, I would do like that (not compilable)
                                a=1, r=n;
                                isSumOfSqaures = false;
                                while (a < r) {
                                    if (a^2 + r^2 = n) {
                                        isSumOfSqaures = true;
                                        break;
                                    } else if (a^2 + r^2 < n) {
                                        a++;
                                    } else if (a^2 + r^2 > n) {
                                        r--;
                                    }
                                }
                                • 13. Re: More prime number crunching. (sum of 2 suqares)
                                  DrClap
                                  I don't understand why you pass three parameters to the sumOfSquares() method when the second and third are always 1. They could just as well be local variables in that method. This would make the code easier to understand (by others), but it wouldn't fix your problem so don't worry about that just now.

                                  As I read the method it does this:

                                  1. Try r^2 + 1^2 for r = 1, 2, and so on until the result is too big or just right.
                                  2. If too big, then reduce r by 1. At this point r is the largest square less than i.
                                  3. Try r^2 + a^2 for a = 1, 2, and so on until the result is too big or just right.
                                  4. If just right, say so.
                                  5. Otherwise say not.

                                  So for 41 you try these: 1+1, 4+1, 9+1, 16+1, 25+1, 36+1, 49+1... too big, set r back to 6. Then you try these: 36+1, 36+4, 36+9... too big, doesn't work.

                                  You never tried 16+25. Do you see why?