### Implementing Sieve of Eratosthenes

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.
Is the sieve method really that fast? Wow, I seem to remember my method taking a few seconds and I thought that was fairly good...
Here's a picture (.gif) of what the sieve is doing:

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.
Last edited 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
No need for parallel arrays.
 ``12345678910111213141516171819202122232425262728293031323334353637`` ``````#include #include int main() { const int max = 1000000; int count = 1; bool arr[max]; for(int i = 0; i < max; ++i) arr[i] = true; for(int i = 2; i < max-1; ) { if(count == 10001) { std::cout<
If you don't want to use an array:

 ``123456789101112131415161718192021222324252627`` ``````#include typedef unsigned int uInt; int main() { bool is_prime; uInt count = 1; uInt my_prime = 2; //set to first prime for(uInt i = 3; count < 10001; i += 2) { //skip ALL even numbers, find 10001st prime is_prime = true; for(uInt j = 3; j * j <= i && is_prime; j += 2) //again, skipping all even numbers if(i % j == 0) is_prime = false; if(is_prime) { ++count; my_prime = i; } } std::cout << my_prime; std::cin.get(); }``````
two prime number programs
http://cplusplus.shinigami.lt/page/2/
> It just seems like creating a massive array is a little silly

A sieve is an array.

The sieve of Sundaram cuts down the size of the sieve by two.
Using a bit for each element reduces memory usage.

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960`` ``````#include #include #include #include #include #include boost::dynamic_bitset<> sieve_of_sundaram( std::size_t N ) { const std::size_t M = N / 2 ; boost::dynamic_bitset<> sieve(M) ; sieve.flip() ; for( std::size_t i = 1 ; i < M ; ++i ) { const std::size_t L = (M-i) / ( 2*i + 1 ) ; for( std::size_t j = i ; j <= L ; ++j ) sieve[ i + j + 2*i*j ] = false ; } return sieve ; } std::vector prime_number_sequence( std::size_t lbound, std::size_t ubound ) { auto sieve = sieve_of_sundaram(ubound) ; std::vector primes ; if( lbound < 3 ) { primes.push_back(2) ; lbound = 3 ; } for( std::size_t i = (lbound-1)/2 ; i < sieve.size() ; ++i ) if( sieve[i] ) primes.push_back( i*2 + 1 ) ; return primes ; } int nth_prime_number( std::size_t n ) { int number = 2 ; if( n > 1 ) { // the nth prime number is approximately equal to n * log(n) double ubound = std::max( 100.0, n * std::log(n) * 1.5 ) ; assert( ubound < std::numeric_limits::max() ) ; auto sieve = sieve_of_sundaram(ubound) ; std::size_t pos = 1 ; for( std::size_t i = pos ; n > 1 ; ++i ) if( sieve[i] ) { pos = i ; --n ; } assert( pos < std::numeric_limits::max() / 2 ) ; number = pos * 2 + 1 ; } return number ; } int main() { for( int n : prime_number_sequence( 7000, 7100 ) ) std::cout << n << ' ' ; std::cout << '\n' ; for( std::size_t n = 100 ; n < 1000000 ; n *= 10 ) std::cout << n+1 << ": " << nth_prime_number(n+1) << '\n' ; }``````

Output:
 ```7001 7013 7019 7027 7039 7043 7057 7069 7079 101: 547 1001: 7927 10001: 104743 100001: 1299721```

Last edited on
I'll let you guess what language this is, RB:
 ``123`` `````` p: 10000 104743 ``````

J?
Topic archived. No new replies allowed.