백준 2960번(Silver 4)

백준 2960번 에라토스테네스의 체에 대한 백준 문제를 풀어보겠습니다.

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

2960번: 에라토스테네스의 체

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

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

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

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

 

기본 에라토스테네스의 체 코드

#include <iostream>
#include <vector>

int main() {
	std::vector<int> tmp(1001, 1);
	int K, N;
	int count = 0;
	std::cin >> N >> K;
	tmp[0] = 0;
	tmp[1] = 0;
	for (int i = 2; i <= sqrt(N); ++i) {
		if (tmp[i] == 0) continue;
		for (int j = 2 * i; j <= N; j += i) {
			tmp[j] = 0;
		}
	}
	return 0;
}

sqrt(N)은 N의 제곱근까지만 찾으면 된다는 소리로, 

N = a * b 일 때, N'이 N의 제곱근이라면 a >= N'이면 b <= N'가 되고, 작은 수 b에서 b의 배수만큼 늘어나는

코드 특성상 모든 N 이하의 소수가 아닌 수를 다 찾을 수 있습니다.

 

백준문제에 대한 코드

#include <iostream>
#include <vector>

int main() {
	std::vector<int> tmp(1001, 1);
	int K, N;
	int count = 0;
	std::cin >> N >> K;
	tmp[0] = 0;
	tmp[1] = 0;
	for (int i = 2; i <= N; ++i) {
		for (int j = i; j <= N; j += i) {
			if (tmp[j] == 0)
				continue;
			else {
				tmp[j] = 0;
				count++;
				if (count == K)
					std::cout << j;
			}
		}
	}
	return 0;
}