get_nth_prime_with_optimized_sieve.cpp

#include <memory>

// note1. 홀수 n이 주어졌을 때, n이 몇 번째 홀수인지 알아내려면 (n - 3) >> 1 한다.
unsigned long get_nth_prime_with_optimized_sieve(unsigned long n) {

	unsigned long precompute_max_count = 200000;

	// prime number를 체크하기 위해 우선 대상이 될 모든 odd number들을 담을 배열을 만든다.
	vector<bool> odd_numbers_divisible(precompute_max_count/2);	// odd numers

	// n개의 prime number들이 담길 array를 만든다.
	auto primes = std::make_unique<unsigned long[]>(n);

	// 3부터 모든 odd numbers에 대하여,
	for (unsigned int i = 3; i <= std::sqrt(precompute_max_count); i += 2)	// 3, 5, 7, 9, 11, 13....9257
	{
		auto i_th = (i - 3) >> 1;	// i_th는 i라는 odd#가 몇 번째 odd number인지 구한다.
		if (odd_numbers_divisible[i_th] == false)	// divide 할 수 없는 prime #찾았다면,
		{
			// prime number를 찾았다면, loop 돌며 이후 i의 위치마다 모두 prime number가 아니라고 체크해 둔다.
			for (unsigned int j = i*i; j < precompute_max_count; j += i)
			{
				// j는 이미 다른 수의 제곱이고 3부터 증가하는 홀수(3,5,6,7...) i 를 더한 값이므로, 
				// j는 prime#가 아니다.	

				if (j & 1)	// odd인 경우에만. even인 경우는 아예 prime #가 아니다.
				{
					// 3번째 odd#는 9, (9-3) >> 1 하면 3
					// 6번째 odd#는 15, (15-3) >> 1하면 6
					// y는 j라는 홀수가 몇 번째 홀수인지를 index를 구한다.
					auto y = (j - 3) >> 1;

					// y번째 odd#는 prime#가 아니다. divide 할 수 있다.
					odd_numbers_divisible[y] = true;
				}
			}
		}
	}

	unsigned long primes_length = std::count(std::begin(odd_numbers_divisible), std::end(odd_numbers_divisible), false) + 1; 
	// odd_numbers_divisible는 3부터 체크하므로 prime number인 2를 하나 더 함

	if (primes_length < n) {
		return 0;
	}

	// 첫번째 prime #는 2다.
	primes[0] = 2;
	unsigned int cnt = 1;
	for (unsigned int i = 0; 2 * i < precompute_max_count && cnt < n; i++)
	{
		if (odd_numbers_divisible[i] == false)
		{
			primes[cnt++] = 2 * i + 3;
			//cout << 2 * i + 3 << " ";
		}
	}
	//cout << endl;

	// [0]에 첫번째 prime이 있으므로 6번째 primn이라면 [6-1] 구해야 한다.
	return primes[n - 1];
}