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

문제링크 : https://boj.kr/2960

시작 숫자부터 해당 숫자만큼의 배수로 탐색하여 답을 찾아가면 된다.

단 한번도 특정 숫자로 나누어 떨어지지 않은 숫자는 모두 소수이고 그 소수의 배수들은 소수가 아닌 수가 된다.

소수를 구하는 알고리즘은 다음과 같다.

처음으로 지워지는 숫자인 파란색은 소수이고 지워진 수는 소수의 N 배수이다. 

배수가 되는 순간 소수가 아니기 때문에 당연히 파란색만 소수가 된다.

<초기 값>

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

<1회 실행> 2의 배수 제거

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

<2회 실행> 3의 배수 제거

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

<3회 실행> 5의 배수 제거 (4의 배수는 이미 제거 됨)

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

<4회 실행> 7의 배수 제거 (5의 배수는 이미 제거 됨)

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

<5회 실행> 11의 배수 제거 (8,9,10의 배수는 이미 제거 됨)

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

<6회 실행> 13의 배수 제거 (12의 배수는 이미 제거 됨)

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

<7회 실행> 17의 배수 제거 (14,15,16의 배수는 이미 제거 됨)

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

<8회 실행> 19의 배수 제거 (18의 배수는 이미 제거 됨)

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

배수를 지워나가면서 놀랍게도 파란색으로 칠해진 숫자(처음으로 지워진 숫자)는 모두 소수임을 알 수 있다.

에라토스테네스의 체는 이런 식으로 소수를 구하는 알고리즘이다.

해당 순서가 지워졌을 경우를 0으로 하였고 지워진 것으로 판단되면 continue 하여 루프를 계속한다.

입력에 해당하는 값이 나왔을 때 루프를 탈출한다.

따로 소수를 구하는 문제가 아니기 때문에 소수를 별도로 저장하진 않았다.

이 문제의 경우 소수를 직접 구하는 문제가 아니라 약간 아쉬운 감이 있다.

코드 하단에 소수 배열을 구하는 부분을 따로 정리해두었다.

// BOJ 2960 에라토스테네스의 체
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    int num, k;
    cin >> num >> k;
    int pnum = 2;
 
    vector<int> arr(num + 1, 0);
    for (int i = 2; i <= num; i++)
        arr[i] = i;
    int cnt = 0;
    int result;
    while (true) {
        for (int i = pnum; i <= num; i += pnum) {
            if (arr[i] == 0)
                continue;
            result = arr[i];
            arr[i] = 0;
            if (++cnt == k)
                goto END;
        }
        pnum++;
    }
    END:
    cout << result;
 
    return 0;
}

소수를 구해서 소수 리스트를 만드는 방법은 아래와 같이 작성하면 된다.

isPrime이라는 배열을 통해 어떤 숫자가 소수인지 아닌지 여부를 체크할 수 있다.

pnum은 소수가 순서대로 담긴 배열이다.

vector <bool> isPrime(maxNum + 1, false);
vector <int> pnum;
 
for (int i = 2; i <= maxNum; i++)
    isPrime[i] = true;
 
for (int i = 2; i <= maxNum; i++) {
    if (isPrime[i]) {
        pnum.push_back(i);
        for (int j = i * 2; j <= maxNum; j += i)
            isPrime[j] = false;
    }
}

위 코드를 활용한 문제는 여기에서 볼 수 있다.