Scroll down to see how it works. If you'd rather solve the problem yourself, don't scroll. . . . . . How it works (this is a spoiler): ========================================= Finding primes is known to be a tricky problem. It can be quite difficult to find them at any reasonable pace (it's been years since we last found a new prime), and there aren't any major shortcuts you can take. However, there are a lot of small optimizations you can make that, when all functioning at once, an result in a decently fast program. That's what we've done here. The obvious, slow method is to go through each number, check all of the numbers below it to see if any of them are its factors (thus making it not prime), and move on. We've done that, except way better. The first optimization you can make is to realize that the only even prime is 2. If we kick-start our list by manually adding 2, we can then skip all the even numbers from there on out. The next optimization is to only check for factors under the square root of the number (any factors above the square root are just part of a pair that has already been checked). Another massive help is to check only the numbers that are already on our prime list. Due to the fact that each number can be broken down into prime factors, we know that if we check all of the primes under the square root of the number, that's enough for a conclusive result. (Keep in mind that we already have a handy list of primes right in front of us...) The final optimization is to stop checking factors once we know a number isn't prime. If we know it's a multiple of 3, there's no reason to check if it's a multiple of anything else. We already know it isn't prime. With all of those layers of optimization, the result is a speedy program that generates primes. All we need to do is stop when the list is 10001 items long. Oh, and one more thing... The program can run in around a minute and fifteen seconds in turbo mode. Can any of you make a faster one? (If you do, please let me know! I'd love to see it.)
The @ProjectEuler account is created and maintained by . If you have questions, feel free to comment here or on my profile page for a much quicker response.
