에라토스테네스의 체 Bj#2960

에라토스테네스의 체 BJ#2960

C++ 코드 보기

#include <iostream>
#include <vector>

using namespace std;

int main() {

	int N, K;
	int cnt = 0;

	cin >> N >> K;

	vector<int> prime;
	prime.resize(N+1);

	for (int i = 2; i <= N; i++) {
		if (prime[i] == 1) continue;
		for (int j = i; j <= N; j += i) {
			if (prime[j] == 0) {
				cnt++;
				if (cnt == K) {
					cout << j;
					break;
				}
				prime[j] = 1;
			}
		}
	}

	return 0;
}

☝ 입력 형식

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

🤞 출력 형식

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

🤟 구현 과정

문제에 에라토스테네스의 체에 관해 잘 설명되어있다.

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

위 단계를 따라 코딩한다면, 쉽게 에라토스테네스의 체에 대해 익힐 수 있다.

🍀 Pain Points

1. 소수의 판별이 필요할 때 자주 사용되는 알고리즘.

개념도 어렵지 않고, 뛰어난 성능으로 정말 자주 사용된다. 꼭 기억해두자.

2. 시간복잡도의 개선이 가능하다?

더 개선하면 O(NloglogN)까지 낮출수 있다고는 하는데..

거기까지 유도하는건 다음 기회에 이어서 진행해봐야겠다.