[SCCC] K번째 소수_15965번

K번째 소수_15965번

코드

#include <bits/stdc++.h>
using namespace std;
vector<int> primenumber;
vector<bool> vec;

//print vector<int> primenumber
void pprint(vector<int> arr) {
    for (int i = 0; i < arr.size(); i++) 
        cout << arr[i] << " ";
    cout << "\n\n";
}

//print vector<bool> vec
void vprint(vector<bool> arr) {
    for (int i = 0; i < arr.size(); i++) 
        cout << arr[i] << " ";
    cout << "\n\n";
}


//true -> primenumber, false -> primenumber X 
void eratos(int start, int end) {
    //Initializing
    for (int i = start; i <= end; i++) {
        vec.push_back(true);
    }

    //eratos
    for (int i = 2; i <= end; i++) {
        if (vec[i]) {
            for (int j = i+i; j <= end; j += i) {
                vec[j] = false;
            }
        }
    }

    //return vector<int>
    for (int i = start; i <= end; i++) {
        if (vec[i]) {
            primenumber.push_back(i);
        }
    }
}

int main() {
    int n;
    cin >> n;

    vec.push_back(false);  //0 is not primenumber
    vec.push_back(false);  //1 is not primenumber
    
    //get primenumber
    int start = 2, end = n;
    while(1) {
        eratos(start, end);
        if (primenumber.size() >= n) break;
        start = end + 1;
        end = end + end;
    }

    cout << primenumber[n-1];
}

풀이노트

• 에라토스테네스의 체 : 소수 구하기

• eratos()
  return 을 vector 말고 vector 로 해서 딱 소수만 전달하자.
  그리고 vector[n-1] 이 답이 됨

• 공간복잡도
  입력값이 4000개 쯤 되므로, 입력값을 찾을 때까지 eratos 메서드를 실행해야 함
  메모리 공간을 줄이기 위해 primenumber 를 계속 공유해야 함
  따라서 한번 찾은 primenumber 는 다시 찾으면 안됨

• logic
  0 1 은 소수가 아니므로 vec 에 false 를 삽입
  2 ~ n 범위의 소수를 찾아서 primenumber 로 삽입
  primenumber 의 길이가 n 보다 크거나 같으면 -> 종료
  primenumber 의 길이가 n 보다 작으면 -> n+1 ~ 2*n 을 찾음
  -- 주의 : eratos에서 2번째 for 문에서 i 값은 2부터 시작해야 함. 소수 구할 때 앞의 값에 영향을 받기 때문 -> 예를 들어 4는 2의 배수이기 때문에 소수가 아님. 따라서 2부터 돌려야 이를 알 수 있음