C++ 에라토스테네스의 체 - 백준 알고리즘

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)

10 7

출력

---

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

9

정답

---

#include <iostream>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int N = 0, K = 0;
	int a[1001] = { 0 };
	int b[1001] = { 0 };

	cin >> N >> K;
	int count = 0;

	for (int i = 2; i <= N; i++)
	{
		for (int j = 1; j*i <= N; j++)
		{
			if (a[i*j] != 1)
			{
				a[i*j] = 1;     // 지워지는 값을 1로 변경
				count++;
				b[count] = i*j; // 지워지는 값과 순서 저장
			}
		}
	}

	cout << b[K] << endl;

	return 0;
}

---