[BOJ 백준] 에라토스테네스의 체(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(1, K) < N ≤ 1000)

출력 : 

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

 

예제 입력 : 

15 12

예제 출력 : 

7

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

C++ 코드 : 

// 에라토스테네스의 체 2960 
#if 1
#pragma warning(disable:4996)
#include <cstdio>

#define MAX (1000+3)

using namespace std;

bool isNotPrimenumber[MAX];	// 기본값 false
int N, K;

int main() {
	// 1. 입력받는다
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &N, &K);

	// 2. 에라토스테네스의 체
	int cnt = 0;	// 지운 횟수 카운트
	for (int i = 2; i <= N; i++) {

		// 1) 이미 지워졌으면 pass
		if (isNotPrimenumber[i] == true) {
			continue;
		}

		// 2) 배수 제거
		for (int j = i; j <= N; j += i) {
			if (isNotPrimenumber[j] == false) {

				isNotPrimenumber[j] = true;
				cnt++;
				
				// K번째 지우는 순간 출력
				if (cnt == K) {
					printf("%d", j);
					return 0;
				}

			}
		}

	}
	
	return 0;
}
#endif