This content has been marked as final.
Show 10 replies

1. Re: Prime number run problem
3004 Dec 15, 2007 12:22 PM (in response to 807601)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 Dec 15, 2007 12:23 PM (in response to 807601)The loop is not infinite, but it's pretty darn big. 
3. Re: Prime number run problem
3004 Dec 15, 2007 12:25 PM (in response to 807601)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 Dec 15, 2007 1:07 PM (in response to 3004)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 Dec 15, 2007 1:11 PM (in response to 807601)aanginOut wrote:
Let's say you're looking at 60
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.
Do you see it now?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

6. Re: Prime number run problem
3004 Dec 15, 2007 1:12 PM (in response to 3004)jverd wrote:
No. Rather, If you want to find out whether 1,000,000 is prime, you only need to test up to 1,000.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. 
7. Re: Prime number run problem
807601 Dec 15, 2007 1:15 PM (in response to 3004)jverd wrote:
Ohhh now I see it, thank you!aanginOut wrote:
Let's say you're looking at 60
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.
Do you see it now?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

8. Re: Prime number run problem
3004 Dec 15, 2007 1:29 PM (in response to 807601)aanginOut wrote:
Cool, I'm glad it makes sense.
Ohhh now I see it, thank you!
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 Dec 15, 2007 2:03 PM (in response to 3004)
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.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); } }

10. Re: Prime number run problem
807601 Dec 15, 2007 2:44 PM (in response to 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.