10 Replies Latest reply: Dec 15, 2007 2:44 PM by 807601 RSS

    Prime number run problem

    807601
      public class Primesum
      {
          public static boolean isPrime(long p)
          {
              for(long y=2; y<=p; y++)
              {
                  if(y<p && p%y==0)
                  {
                      return false;
                  }
              }
              return true;
          }
          
          public static void main(String[] args)
          {
              long sum = 0;
              for(long i = 2; i < 1000000; i++)
              {
                  if(isPrime(i))
                  {
                      sum += i;
                  }
              }
              System.out.println(sum);
          }
      }
      This is my code for a tiny little program that finds the sum of all prime numbers in a certain range. It works for smaller numbers, i.e. when i make the end condition of the for loop i<10, i get a correct answer (17). I also get 77 when i make the end condition i<20. However, I'm trying to find the sum of primes under one million, but when I run the code, it just runs and runs. I let it run for 5 - 10 minutes and gave up. Is this normal, and I'm just impatient, or did I do something wrong that's putting it in some sort of infinite loop?
        • 1. Re: Prime number run problem
          3004
          This is O(n^2). So when you go from 10 to 1 million, the range expands by a factor of 100,000, and therefore the number of operations expands by a factor of 100,000^2, which is 10,000,000,000. If 10 takes 1 ms., 1 million will take about 4 months.
          • 2. Re: Prime number run problem
            807601
            The loop is not infinite, but it's pretty darn big.
            • 3. Re: Prime number run problem
              3004
              Here's one hint: You don't need to test every number up to the possible prime. You only have to go up to the square root of the possible prime. Do you understand why?
              • 4. Re: Prime number run problem
                807601
                I'm trying to understand...something about square roots of primes being irrational? I'm really confused as to how testing all numbers up to 1000 would give me all the primes up to 1,000,000.
                • 5. Re: Prime number run problem
                  3004
                  aanginOut wrote:
                  I'm trying to understand...something about square roots of primes being irrational? I'm really confused as to how testing all numbers up to 1000 would give me all the primes up to 1,000,000.
                  Let's say you're looking at 60
                  1 * 60
                  2 * 30
                  3 * 20
                  4 * 15
                  5 * 12
                  6 * 10
                      ---- sqrt ~= 7.746
                  10 * 6
                  12 * 5
                  15 * 4
                  20 * 3
                  30 * 2
                  60 * 1
                  Do you see it now?
                  • 6. Re: Prime number run problem
                    3004
                    jverd wrote:
                    aanginOut wrote:
                    I'm trying to understand...something about square roots of primes being irrational? I'm really confused as to how testing all numbers up to 1000 would give me all the primes up to 1,000,000.
                    No. Rather, If you want to find out whether 1,000,000 is prime, you only need to test up to 1,000.
                    • 7. Re: Prime number run problem
                      807601
                      jverd wrote:
                      aanginOut wrote:
                      I'm trying to understand...something about square roots of primes being irrational? I'm really confused as to how testing all numbers up to 1000 would give me all the primes up to 1,000,000.
                      Let's say you're looking at 60
                      1 * 60
                      2 * 30
                      3 * 20
                      4 * 15
                      5 * 12
                      6 * 10
                      ---- sqrt ~= 7.746
                      10 * 6
                      12 * 5
                      15 * 4
                      20 * 3
                      30 * 2
                      60 * 1
                      Do you see it now?
                      Ohhh now I see it, thank you!
                      • 8. Re: Prime number run problem
                        3004
                        aanginOut wrote:
                        Ohhh now I see it, thank you!
                        Cool, I'm glad it makes sense.

                        Note, however, that it could still take anywhere from several minutes to several hours. You might want to put in a print statement every 1,000 or 10,000 or so, just so you can see the progress. Note that as you get further along, it will slow down, because it will have to check more candidate factors for, say, 200,000 than for 20,000.
                        • 9. Re: Prime number run problem
                          807601
                          public class Primesum
                          {
                              public static boolean isPrime(double p)
                              {
                                  
                                  double square = Math.sqrt(p);
                                  for(double y=2.0; y<=square; y++)
                                  {
                                      if(p%y==0.0)
                                      {
                                          return false;
                                      }
                                  }
                                  return true;
                              }
                              
                              public static void main(String[] args)
                              {
                                  double sum = 0.0;
                                  for(double i = 2.0; i < 1000000.0; i++)
                                  {
                                      if(isPrime(i))
                                      {
                                          sum += i;
                                      }
                                  }
                                  System.out.println(sum);
                              }
                          }
                          That's my code now, and it worked, I got the correct answer (3.7550402023E10). Actually it didn't take that long, only about 5 or 6 seconds. Thanks a lot guys.
                          • 10. Re: Prime number run problem
                            807601
                            You are only testing integer values, so you can use int rather than double. (square will have to be double, and sum a long)

                            Summing the primes up to 3 million was faster this way.