[백준] 15965번 - K번째 소수 (실버 2)

1. 문제

https://www.acmicpc.net/problem/15965

15965번: K번째 소수

---

2. 코드

#include <iostream>
#include <cstring>

using namespace std;

bool *Sieve_of_Eratosthenes(int m) {
    bool* arr = new bool[m + 1];

    memset(arr, 1, sizeof(bool) * (m+1));
    arr[0] = false;
    arr[0] = false;

    for (int i = 2; i < m + 1; i++) {
        if (arr[i] == true) {
            for (int j = i * 2; j < m + 1; j += i) {
                arr[j] = false;
            }
        }
    }

    return arr;
}


int main() {
    int a, max = 50000000, sum=0;
    bool* arr = Sieve_of_Eratosthenes(max);
    cin >> a;

    for (int i = 0; i <= max; i++) {
        sum += arr[i];
        
        if (sum == a+1) {
            cout << i << endl;
            break;
        }
    }
    
    return 0;
}

---

3. 결과

---

4. 리뷰

• 에라토스테네스의 채 알고리즘을 사용하여 충분히 큰 소수 범위의 소수 여부 배열을 생성함.
• 해당 여부가 1인 경우(소수인 경우)를 누적하여 원하는 위치의 소수를 찾음
• 100점 통과는 가능했지만 좀 더 효율적인 방법이 필요함.