Everyone's done this one. I mean, well, most people have. But today I read a post by a guy who just finished this for the first time (and congratulations, by the way!), and he said his implementation took six hours to run.
So, in the spirit of XKCD 1053, here's to today's lucky 10,000! If you find this one boring, I'm sorry. Go to Hooters or something. Jeez.
Find the sum of all primes less than two million.
I'm not quoting Project Euler; this is my own definition. Theirs may or may not include two million. I don't care. It doesn't matter. Two million isn't all that prime anyway. And I say "You-ler," usually, not "Oiler." Bite me.
The fastest way to do this is with something called a sieve, but, to be realistic, most beginning programmers can't write a sieve. The naive way is to check each number to see if it can be divided evenly by any number smaller than it—which is
O(N * N) and takes forever, as our hero of the hour discovered last night.
Your task is to write this program in such a way as to allow it to finish in the space of one good TV commercial.
For those of you who are a little more experienced, consider whether it is possible in your language of choice to improve the performance of the naive form of this algorithm by employing multiple processor cores, threads, unicorns, or what have you. Note: for our purposes, "naive" does not mean you can't limit your search space using something more reasonable than "any number less than N."
You could just Google this, so I'm just going to write it here: