So, I've been project euler problems lately, and hit one that asks for the 10,001st prime number. After some research, it seems as if a sieve is the way to go. Though, I'm not sure how to implement it. I was originally thinking of making a struct to hold a hold a number, and a bool saying whether it's composite or not. Though this would require making probably 100k plus objects of this, and that definitely seems pretty slow and sloppy. Any suggestions?
Couldent you just calculate all the prime numbers up to 10001st prime number using the modulus operator and submit that? Or dose your problem explicity ask for ONLY the 10001st prime number?
I can understand that you might want to implement the Sieve method for the sake of it, but for this problem it certainly isn't necessary.
I suggest:
iterate through numbers
if the number is prime (check using a function), increase the count of primes
if the number of primes is 10001, output the current number
I solved this problem a long time ago, and what I remember I did was to use an array of booleans, and to apply the algorithm of the sieve and set a position to true if it was a prime. It ran pretty fast, and I remember the runtime was less than a second... and that's saying something, considering I wrote it in Java.
Never done this myself. Seems like you make a bool array (much larger than 10001), and set everything to true. Then consider the index in the array to be the number you are checking:
I don't know if you're reading this, but I've learned as I posted.
Make yourself a very large bool array and set all of the values to true. The integer you deal with is the index in the array. [0] and [1] don't count, our first prime is [2].
2 is prime, which means that 4,6,8... is not prime, so go through the array setting every multiple of 2 to false. Then increase your counter to 3, look at if it is true. Since it is, every index that is a multiple of three is false. Then go through looking for true, so skip over 4 and find 5.... Repeat
It's proven that when you increase your index looking for "true", the index you find is a prime number. There is no math type math going on.
It just seems like creating a massive array is a little silly. And having basically parallel arrays like a couple of you described seems to be the exact same as my vector of struct idea.
Either one seems sloppy to me, but I can't see a better to do it.
And thanks for the link LowestOne, though I have already seen it. Wikipedia is actually the only place I've looked at this algorithm at lol