[백준 2960] 에라토스테네스의 체

문제링크 입니다

🚀 [에스토스테네스의 체] 문제 😊😊😊😊😊

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

• 2부터 N까지 모든 정수를 적는다.
• 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
• P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
• 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

🔑 [풀이]

에스토스테네스의 체는 우선 2부터 n까지의 수를 컨테이너에 모두 쓴 상태에서 컨테이너를 순회하면서 지워지지않은 목록들을 지워나갑니다. ex) 2를 제외한 n이하의 모든 2의 배수들을 컨테이너에서 제거합니다. 다음 제거되지않은 3의 제외한 3의 배수들을 컨테이너에서 지워갑니다.

⌨️ 입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(1, K) < N ≤ 1000)

🖥 출력

첫째 줄에 K번째 지워진 수를 출력한다.

🖱 입력 예제

15 12

💻 출력 예제

7

💎 전체 코드는 다음과 같습니다.

//
//  2960.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/11/12.
//

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n,k;
    cin >> n >> k;
    vector<bool> vec(n+1, true);
    vec[0] = false;
    vec[1] = false;
    int count = 0;
    for(int i=2; i<n+1 ; i++){
        if(vec[i]){
            for(int j=i; j< n+1;j+=i)
                if(vec[j]){
                    vec[j] = false;
                    count++;
                    if(count == k){
                        cout << j;
                        return 0;
                    }
                }
        }
    }
    return 0;
}