[백준] 2960번 에라토스테네스의 체 -C++

문제

2960번 에라토스테네스의 체

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

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

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

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

입력

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

출력

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

예제 입력 1

7 3

예제 출력 1

6

예제 1:

1. 7까지의 정수: 2, 3, 4, 5, 6, 7
2. 지우지 않은 수 중 가장 작은 수 P: 2 → 소수
3. 2를 지우고 2의 배수들을 크기 순으로 지운다. → 4, 6 지움
4. 3의 배수→ 5의 배수 지우기…

2→ 4→ 6→3 순으로 지워져서 3번째 지워지는 수는 6

---

문제 요약:

입력 받은 정수 N까지의 소수를 찾는 알고리즘 에라토스테네스의 체에서 K번째로
지워지는 수 찾기

🤔 생각해야할 점:

🎯 에라토스테네스의 체:

1과 자기자신 외에는 나눠지는 수가 없는 것이 소수이므로 가장 작은 소수부터 검사해서 그 소수의 배수들은 제거하면 소수를 찾을 수 있다.

• 에라토스테네스의 체 알고리즘으로 가장 작은 소수를 지우고 그 수의 배수들도
  거른다.

  **가장 작은 소수는 항상 2다** 

풀이 방법:

• 소수를 찾을 범위 N과 지워지는 순서 K를 입력받는다.
• 소수인지 여부를 판별할 벡터 prime을 만들어서 true로 초기화 true이면 아직 방문하지 않은 수, false면 이미 방문한 수(지워진 수)
  
• 2부터 N까지 의 수를 먼저 검사해서 false(이미 방문)이면 컨티뉴
• i의 배수들을 검사해서 false로 바꿔주고 이러면 체에 걸러지는 것이니까 K를 감소해준다.
• K가 0이 되면 K번째 수를 찾은 것~!

내가 작성한 코드

#include <iostream>
#include <vector>

using namespace std;

int Prime(int n, int k){
    vector<bool> prime(n+1, true);

    for(int i=2; i<=n; i++){ //i는 2부터 n까지의 수
        if(prime[i] == false) 
            continue; 

        for(int j=i; j<=n; j += i){ //i의 배수 j
            if(prime[j] == true) { //아직 지우지 않은 수는 
                prime[j] = false; //지워준다.
                k--;
                if(k == 0) 
                    return j; //k번째라면 인덱스를 리턴
            }
        }
    }
    return -1;
}

int main(){

    int N, K;
    cin >> N >> K;
    cout << Prime(N,K) << endl;

    return 0;
}

 for(int j=i; j<=n; j+= i) :

에라토스테네스의 체 개념의 핵심, i번째 인덱스부터 i 의 배수씩 증가시켜서 배수들을 검사