[BaekJoon 2960번] 에라토스테네스의 체(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

2960번: 에라토스테네스의 체

 

 

[문제 설명]

 

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

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

2부터 N까지 모든 정수를 적는다.
아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

 

 

[입력]

 

 

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

 

 

[출력]

 

 

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

 

 

[입출력 예]

 

 

입력	출력
7 3	6
15 12	7
10 7	9

 

 

[문제 풀이]

 

 

[Algorithm] 에라토스테네스의 체

 

문제를 잘 읽고 에라토스테네스의 체 알고리즘을 구현하면 풀 수 있는 문제이다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>
using namespace std;
/* 
2부터 N까지 모든 정수를 적는다.
아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
*/
int N, K;
bool ischecked[1001];
int primecnt = 0;

void removeNumber(int N) {
    // 에라토스테네스의 체 적용
    ischecked[1] = false; // 소수 아님
    for(int i = 2; i <= N; ++i) {
        if(!ischecked[i]) continue; // 소수가 아닌 값들은 제외
        primecnt += 1;
        if(primecnt == K) cout << i;
        for(int j = i * i; j <= N; j += i) {
            if(ischecked[j]) {
                // 아직 지우지 않은 배수들을 크기 순서대로 지운다
                ischecked[j] = false;
                primecnt += 1;
                if(primecnt == K) cout << j;
            }
        }
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K; // N은 수의 범위, K는 K번째 지우는 수
    fill(ischecked, ischecked + 1001, true); // 모든 수가 소수라 가정
    removeNumber(N);
}