백준 15965 - K번째 소수

필요 지식

이 문제는 소수 정리를 알면 매우 단순해진다.

풀이

소수 정리에 의해 ${e^{16} \over 16} \approx 555381$를 계산할 수 있고 $e^{16}$ 정도의 범위는 에라토스테네스의 체로 충분히 계산할 수 있음을 알 수 있다.

 

체를 돌려 50만번째 소수까지 찾아 출력하도록 하면 된다.

 

전체 코드 - 여기서는 linear sieve를 사용했다.

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
 
using namespace std;
 
vector<vector<int>> linear_sieve(int n) {
  vector<int> spf(n + 1), prime_set;
 
  for (int i = 2; i <= n; ++i) {
    if (!spf[i]) {
      prime_set.push_back(i);
      spf[i] = i;
    }
 
    for (int j = 0; (long long)i * prime_set[j] <= n; ++j) {
      spf[i * prime_set[j]] = prime_set[j];
      if (i % prime_set[j] == 0)
        break;
    }
  }
 
  return { prime_set, spf }; // 0: prime numbers, 1: spf
}
 
void solve()
{
  int n;
  cin >> n;
 
  auto res = linear_sieve(8888888);
  cout << res[0][n - 1];
}
 
int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록