[알고리즘] 백준 알고리즘 2960번 : 에라토스테네스의 체(C++ 풀이)

 

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(2, K) < N ≤ 1000)

 

- 출력

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

 

- 예제

 

- 풀이

예를들어 1 ~ 100까지의 수들 중에서 소수를 찾는다고 가정해 보겠습니다.

2부터 시작하여 소수가 아닌 수들을 지워 나가기 시작하겠죠.

그렇게 지우다 보면 11까지 오게 됩니다. 11은 지금까지 지워지지 않았으니 소수로 판단합니다.

그럼 11의 배수들을 지워야 하는데 11의 배수들 부터는 굳이 수행할 필요가 없게 됩니다.

이미 11보다 작은 수들을 체크하는 부분에서 11의 배수들을 모두 지웠기 때문이죠.

(2X11, 3X11, 4X11 등)

지워지지 않은 수의 배수들을 지우는 과정은 주어진 범위의 제곱근 까지만 수행하면 되겠습니다.

 

본 문제는 k 번째로 지워진 수를 출력하는 것이므로 해답은 아래 소스코드와 같습니다.

 

- 소스코드

#include<iostream>
#include<string>
#include<stdlib.h>
#include<stdio.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int input, a;
	cin >> input >> a;
	int arr[1001] = { 0 };
	vector<int> v;	//지워진 수 저장
	for (int i = 1; i <= input; i++) {
		arr[i] = i;
	}
	arr[0] = 1;
	arr[1] = 1;
	for (int i = 2; i <= input; i++) {
		if (arr[i] != -1) {
			v.push_back(arr[i]);
			for (int j = i+1; j <= input; j++) {
				if (arr[j] % arr[i] == 0) {
					v.push_back(arr[j]);
					arr[j] = -1;
					
				}
			}
			arr[i] = -1;
		}
	}
	cout << v[a-1];
}