Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#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];
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.