Implementing Sieve of Eratosthenes

[ResidentBiscuit]

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?

[Owain]

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?

[georgep]

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

[packetpirate]

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.

[georgep]

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...

[Lowest0ne]

Here's a picture (.gif) of what the sieve is doing:
http://upload.wikimedia.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif

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.

[ResidentBiscuit]

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

[naraku9333]

No need for parallel arrays.

#include <iostream>
#include <fstream>
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<<i;
			break;
		}
		//mark all multiples
		for(int j = 2; (j*i) < max-1; ++j)
		{
			arr[i*j] = false;
		}
		//find next prime
		for(int k = i+1; k < max-1; k++)
		{
			if(arr[k])
			{				
				i=k;
				++count;
				break;
			}	
		}
	}

	return EXIT_SUCCESS;
}

[MetalMilitia]

If you don't want to use an array:

#include <iostream>

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();
}

[Shinigami]

two prime number programs
http://cplusplus.shinigami.lt/page/2/

[JLBorges]

> 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.

#include <vector>
#include <boost/dynamic_bitset.hpp>
#include <cmath>
#include <limits>
#include <cmath>
#include <iostream>

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<int> prime_number_sequence( std::size_t lbound, std::size_t ubound )
{
    auto sieve = sieve_of_sundaram(ubound) ;
    std::vector<int> 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<std::size_t>::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<int>::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

[Catfish2]

I'll let you guess what language this is, RB:

   p: 10000
104743
   

[Zephilinox]

J?