백준 알고리즘 2960번 에라토스테네스의 체

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

문제

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

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

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

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

입력

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

출력

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

풀이

문제에서 P(아직 지우지 않은 수 중 가장 작은 수)를 찾아서, P와 P의 배수를 지워야 한다. 나는 값을 지우는 대신 P와 P의 배수를 1로 바꾸어주는 방법을 썼다.

N을 입력받아서 2부터 N까지 값을 가지는 배열을 만든다. 그리고 배열에서 값이 1인 것의 개수를 세어서 num 이라는 변수에 저장하고, num이 0보다 큰 경우 (즉 아직 모든 수를 지우지 않은 경우), 반복문을 돌면서 에라토스 테네스의 체 알고리즘을 반복한다.

코드

#include <iostream>

using namespace std;

int main() {
    int N, K, index=2;
    int num = 0; // array[i] = 1인 것의 개수
    int count = 0; // 몇번째로 지우는 것인지 세기

    cin >> N >>  K;
    int array[N];
    int min = N;

    for (int i=0;i<N-1;i++) {
        array[i] = index++;
        if (array[i] != 1) {
            num++;
        }
    }

    // 아직 모든 수를 지우지 않았다면 (= 값이 1인 것의 개수가 >0 이라면) 반복한다. 
    while (num >= 1) {
        // 가장 작은 값P 찾기 = min
        min = N;
        for (int i=0;i<N-1;i++) {
            if (array[i] != 1 && array[i] < min) {
                min = array[i];
            }
        }
	
        // min과 min의 배수를 차례대로 지운다. (= 값을 1로 바꾼다.)
        for (int i=0;i<N-1;i++) {
            if (array[i] % min == 0) {
                // 몇번째로 지우는 (1로 바꾸는) 것인지 센다. 
                count++;
                // K번째로 지우는 수를 찾아야 하므로, count가 K와 같다면 그 배열의 값이 답이 된다. 
                if (count == K) {
                    cout << array[i];
                    return 0;
                }
                array[i] = 1;
            }
        }

        // 아직 지우지 않은 것(= 1로 바뀌지 않은 것)이 몇개인지 센다. 
        num = 0;
        for (int i=0;i<N-1;i++) {
            if (array[i] != 1) num++;
        }

    }

}