[C++] 백준 2960번 에라토스테네스의 체

1. 문제이해

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

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

 

 

다음과 같은 규칙을 따르되,

N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 구현하는 것이 목표이다.

 

1. 2부터 N까지 모든 정수를 적는다.

2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.

3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.

4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

 

 

 

2. 문제풀이

 

2부터 N까지의 자연수를 입력받고, K번째 지워지는 숫자를 찾는 문제이다.

단, 단순히 소수를 찾는 문제가 아닌,

소수를 찾고 지우는 과정에서 지워지는 수를 찾는 점이라는 것에 유의해야한다.

 

즉, 위와 같은 규칙에 따라 수들이 지워질 때마다 count라는 변수를 +1해주고,

해당 변수의 값이 주어진 K값과 같아지면 그때의 지워진 값을 출력하고 종료하면된다.

 

자세한 코드는 아래를 참고하자.

 

 

 

3. 소스코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int N, K;
	vector <int> v;
	int P;
	int erase;
	int count = 0;

	cin >> N >> K;
	// 1. 2부터 N까지의 모든 정수를 적는다.
	for (int i = 2; i <= N; i++) {
		v.push_back(i);
	}
	
	while (1) {
		// 2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 
		//    이것을 P라고 하고, 이 수는 소수이다.
		P = v[0];
		// 3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
		for (int i = 0; i < v.size(); i++) {
			if (v[i] % P == 0) {
				erase = v[i];
				v.erase(v.begin() + i);
				count++;
				// 4. 만약, K번째 수까지 지웠다면 해당 수를 출력한다. 
				if (count == K) {
					cout << erase;
					return 0;
				}
			}
		}
	}

	return 0;
}

작성한 코드는 위와 같다.

2부터 N까지의 모든 정수를 벡터 v에 저장하고, while문을 이용해 K번째 지워지는 수를 찾는다.

 

while문 안의 내용은 문제에서 주어진 에라토스테네스의 내용과 동일하다.

지워지지 않은 수 중 가장 작은 수를 찾아 P라고 두고, 

for문을 이용해 P의 배수를 차례대로 지워나간다.

 

이때, erase, count라는 변수를 따로 두었는데,

두 변수는 각각 그때마다 지워지는 값과 몇번째 지워지는 수인지를 저장하는 변수이다.

count 값이 주어진 K값과 같아지면, 그때 지워진 값인 erase를 출력하고 종료한다.

 

 

---