[백준 알고리즘] 2960번 : 에라토스테네스의 체 (C++) 문제 풀이

문제

에라토스테네스의 체는 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번째 지워진 수를 출력한다.

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #2 2번

• 문제를 번역한 사람: baekjoon
• 잘못된 조건을 찾은 사람: djm03178
• 문제의 오타를 찾은 사람: jh05013, moonhi123

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

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

 

문제풀이

에라토스테네스의 체는 풀이보다는 본인이 직접 해보면서 이해해야하는 부분이 크기에 딱히 풀이는 적지않았다.

백준알고리즘을 이용하다보면 소수문제가 많이 보일텐데 에라스토스테네스의 체를 자주 이용하길 바란다.

문제풀이가 정말 쉬워진다.

 

내 소스 코드

#include <iostream>
#include<vector>
using namespace std;
int n, k;
bool arr[1001];
int cnt = 0;
int main() {
    cin >> n >> k;
    if (k == 1) {
        cout << 2;
        return 0;
    }
    for (int i = 2; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            if (!arr[j]) {
                arr[j] = true;
                cnt++;
            }
            if (cnt == k) {
                cout << j;
                return 0;
            }
        }
    }
 
 
 
    return 0;
}