#include <iostream>
#include <vector>
#include <ctime>
const unsigned long MAX_PRIME = 0x19999998;
unsigned long get_prime_by_sieve( unsigned long number )
{
	if ( number == 1 )
		return 2;
	std::vector<bool> sieve = std::vector<bool>( number * 10, 0 );
	unsigned long i = 0;
	size_t sieve_size = 2 * sieve.size();
	for( unsigned long counter = 1; counter < number; ++counter )
	{
		while( sieve[ ++i ] );
		unsigned int np = 2 * i + 1;
		for( unsigned long j = np * np; j < sieve_size; j += np )
			if ( j & 1 )
				sieve[ j >> 1 ] = true;
	}
	return 2 * i + 1;
}
unsigned long get_prime_by_barmaglot( unsigned long number )
{
	if ( number == 1 )
		return 2;
	std::vector<unsigned long> found_primes( 1, 2 );
	found_primes.reserve( number * 10 );
	unsigned long i = 3;
	for( unsigned long counter = 1; counter < number; i += 2 )
	{
		unsigned long j = 0;
		for( ; j < found_primes.size(); ++j )
			if ( i % found_primes[j] == 0 )
				break;
		if ( j == found_primes.size() )
		{
			found_primes.push_back( i );
			++counter;
		}
	}
	return i - 2;
}
int main()
{
	std::cout << "Berechnung der millionsten Primzahl" << std::endl;
    clock_t start = clock();
	unsigned long prime = get_prime_by_sieve( 1000000 );
	double elapsed = (double)( clock() - start ) / CLOCKS_PER_SEC;
	std::cout << "Sieve, Primzahl: " << prime << " time elapsed: " << elapsed << std::endl;
	start = clock();
	prime = get_prime_by_barmaglot( 1000000 );
	elapsed = (double)( clock() - start ) / CLOCKS_PER_SEC;
	std::cout << "Barmaglot, Primzahl: " << prime << " time elapsed: " << elapsed << std::endl;
}

unsigned long get_prime_by_barmaglot( unsigned long number )
{
	if ( number == 1 )
		return 2;
	std::vector<unsigned long> found_primes( 1, 2 );
	found_primes.reserve( number );
	unsigned long i = 3;
	for( unsigned long counter = number - 1; counter; i += 2 )
	{
		for( unsigned long j = 0; j < found_primes.size(); ++j )
			if ( i < found_primes[j] * found_primes[j] ||  i % found_primes[j] == 0 )
				break;
		found_primes.push_back( i );
		--counter;
	}
	return i - 2;
}