BOJ(C++) / 백준 2960 : 에라토스테네스의 체

백준 2960 : 에라토스테네스의 체

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

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

 

코드

//백준 2960 에라토스테네스의 체
#include <iostream>
#include <vector>
#include <iostream>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, K;
	cin >> N >> K;

	bool visit[1001] = { false, };
	int cnt = 0; 
	for (int i = 2; i <= N; i++) {
		if (visit[i] == true)
			continue;
		for (int j = i; j <= N; j += i) {
			//이미 지워지지 않았을 때
			if (visit[j] == false) {
				visit[j] = true;
				cnt++;
				//K번째 지워질 때 
				if (cnt == K) {
					cout << j << "\n";
					return 0; //종료
				}
			}
		}
	}

	return 0;
}

 

설명

 

위키백과 - https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체는 소수를 찾는 방법이다. 위의 그림과 같이 작동한다. 

 

• visit 방문을 확인하는 배열을 선언한다. 방문이 되었으면 true, 방문이 되지 않았으면 false이다.
• 2부터 아직 방문하지 않은 수 중 가장 작은 수(P)를 찾는다.
• P의 배수를 하나씩 지운다. 이때 이미 방문한 수는 이미 지워진 것이므로 방문하지 않은 수만 지운다.
• 지울 때마다 카운트를 세어 K번째 지워진 수를 출력하고 종료한다. 

 

고찰

처음 문제를 보고 구현했을 때 벡터로 구현하려 했지만 find, erase함수 등을 써야해서 복잡해서 그 방법을 포기하고 visit배열을 활용하여 문제를 구현하였더니 간단하게 문제를 풀 수 있었다. 앞에 삽질을 뺏더라면 쉽게 구현했을텐데 또 하나의 과정이니까 좋게 생각해야겠다.

 

난이도

Silver 4