10 replies to this topic

[JewFro297]

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.


How exactly can I do that other than a loop that tests every number 1 - 2mil? cuz I let that run for an hour and it didnt ever finish... maybe there was an overflow?

[Feral]

Yes the only way to do it would be to loop through each number starting with 2 (because 0 and 1 are always not prime numbers).

If you let it run for an hour and it still wasn't finished then either you are doing it on a calculator or you have and error in your code.

[ZekeDragon]

No, that's not at all true Feral. JewFro, you can look at TkTech's Sieve of Eratosthenes, set NumberToFind to 2000000 and then loop through the results using the TestBit macro to test each value and check if it's prime. If it is, add that to the total so far, which you should look at GMP to contain large numbers like that. If you don't like GMP, a long long might be sufficient... and if not you can do something like this:

totalCheck = totalSoFar + primeNum;
if (totalCheck < totalSoFar || totalCheck < primeNum)
{
    /* There was an overflow */
    overFlowLong += 1;
}
totalSoFar = totalCheck;

Then check overFlowLong to tell you how many times totalSoFar overflowed.

[Feral]

I'm sorry but what exactly about what I said wasn't true?

The only way to iterate over a series of numbers is a loop unless you know of something else and and 0 and 1 are never going to be prime numbers.

Also 2 is the only prime number that is also an even number.

[JewFro297]

He means my way isn't the only way, and that it would be optimized by sieve, thanks btw

[Ewe Loon]

Here's a way to speed things up,
create an array to hold known prime numbers, then you only need to check to see if the test number will divide by them
also you can start the array with 2 already in it then you dont have to check any even numbers (so there is only 1000000 to check rather than 2000000)

1 is not a prime number, I wasnt sure so i looked it up and the reason as explained by wikipedia is

The importance of this theorem is one of the reasons for the exclusion of 1 from the set of prime numbers. If 1 were admitted as a prime, the precise statement of the theorem would require additional qualifications, since 3 could then be decomposed in different ways

3 = 1 · 3 and 3 = 1 · 1 · 1 · 3 = 1³ · 3.

Edited by Ewe Loon, 04 March 2010 - 12:12 AM.

[Ewe Loon]

Total on this post is incorrect, explanation is posted below

I wrote a quick delphi program using the 2 suggestions i mentioned it took 6 minutes 50.5 seconds to calculate all the prime numbers between 1 and 2000000
( PC spec is quad core 2.4GHz )
my prog says their are 148933 prime numbers between 1 and 2000000;
since this is probably for a school assignment I wont give the exact total but my prog said 11799081## ( last 2 digits have been replaced with '#')





there is an interesting animation on this webpage http://en.wikipedia....rimality_of_one

Edited by Ewe Loon, 04 March 2010 - 02:01 PM.

[Hreno]

It is stated on the Project Euler that the program should not run more than 1 minute. So it should be further optimized.

[Ewe Loon]

WOW , i wrote another one, based on the method from the website i posted above
got the same number of prime numbers, got the same total, but it took 0.015 seconds, is that fast enough ?

[Ewe Loon]

I was so impressed i changed it to calculate all the primes between 1 and 200,000,000 , it took 12 seconds,
there are 1,1078,937 primes totalling 792,149,798

this is weird, I edited this post and wrote another one,, both editing and other post are missing

The totals in previous posts are incorrect because the integer was overflowing, i had to change it to int64

142,913,828,9## (last 2 digits replaced with '#' as this is probably someone's school project)
total for primes 1 - 200 million is 1,075,207,199,997,334

Edited by Ewe Loon, 04 March 2010 - 08:56 PM.
error in total

[joyo]

So interesting problem, waitting for the optimization code.