[백준] 수학 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번째 지워진 수를 출력한다.

Approach

사용 알고리즘: 에라토스테네스의 체

• 2부터 n까지 담는 배열을 정의한다
• 반복문을 이용해서 2부터 n까지 지워지지 않은 수를 확인한다
• 지워지지 않은 수에 대해서 그의 배수를 전부 지운다
• 이 과정을 반복하면서 지울 때마다 result++
• result값이 k랑 같아지면 break하고 정답 출력

Source Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <sstream>
using namespace std;



int main()
{
    int n, k;
    cin >> n >> k;
    
    // 2부터 n까지의 수를 담는 배열 
    int prime[1001];
    for (int i = 2; i <= n; i++)
    {
        prime[i] = i;
    }
    
    int result = 0;
    
    // 2부터 n까지 지워지지 않은 수에 대해서 실행
    for (int i = 2; i <= n; i++)
    {
    	// 지워졌으면 무시
        if (prime[i] == 0)
            continue;
        else
        {
        	// 지워지지않은 수면 해당 수부터 그 수의 배수를 전부 지움
            for (int j = i; j <= n; j += i)
            {
                if (prime[j] != 0) // 지워지지않은 수에 대해서만 실행
                {
                    prime[j] = 0;
                    result++; // 지울 때마다 결과 ++
                }
                if (result == k) // k랑 같아지면 break하고 정답 출력
                {
                    cout << j << '\n';
                    break;
                }
            }
        }
    }
    
    
    return 0;
}