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?
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.  and  don't count, our first prime is .
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.