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

# Prime number run problem

``````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
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
The loop is not infinite, but it's pretty darn big.
• ###### 3. Re: Prime number run problem
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
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
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
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
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
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
``````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
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.