[Baekjoon/C++] 31216번 - 슈퍼 소수

[백준] Baekjoon Online Judge

문제로 이동

 

문제

소수는 수학을 사랑하는 누구에게나 매우 중요한 개념입니다. 1보다 크면서 약수가 1과 자기 자신뿐인 자연수를 소수라고 부릅니다. 흐즈로는 소수 중에서도 더욱 특별한 소수가 있다고 생각했습니다.

다음을 만족하는 소수 p를 슈퍼 소수라고 부릅니다.

• 소수 p가 모든 소수 중 k번째로 작은 소수라고 합시다. 이때 k가 소수임을 만족합니다.

정수 n이 주어질 때, 모든 슈퍼 소수 중 n번째로 작은 것을 출력하는 프로그램을 작성하세요.

 

입력

첫 번째 줄에 테스트 케이스의 개수 T가 주어집니다. (1 <= T <= 1000)

그다음 줄부터 총 T개의 줄에 각각 정수 n이 한 줄에 하나씩 주어집니다. (1 <= n <= 3000)

 

출력

각 테스트 케이스에서 입력된 n에 대해 n번째 슈퍼 소수를 한 줄에 하나씩 출력하세요.

 

---

풀이

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

#define MAX 318138

bool arr[MAX];
vector<int> super;

void init();

void init() {
	// 소수 찾기
	arr[1] = true;
	for (int i = 2; i < sqrt(MAX); i++) {
		if (arr[i]) continue;

		for (int j = i * i; j < MAX; j += i) arr[j] = true;
	}

	// 슈퍼 소수 찾기
	int cnt = 0;
	for (int i = 2; i < MAX; i++) {
		if (!arr[i]) {
			cnt++;

			if (!arr[cnt]) super.push_back(i);
		}
	}
}

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

	init();

	int T;
	cin >> T;

	while (T--) {
		int n;
		cin >> n;

		cout << super[n - 1] << '\n';
	}

	return 0;
}

 

void init() {
	// 소수 찾기
	arr[1] = true;
	for (int i = 2; i < sqrt(MAX); i++) {
		if (arr[i]) continue;

		for (int j = i * i; j < MAX; j += i) arr[j] = true;
	}

	// 슈퍼 소수 찾기
	int cnt = 0;
	for (int i = 2; i < MAX; i++) {
		if (!arr[i]) {
			cnt++;

			if (!arr[cnt]) super.push_back(i);
		}
	}
}

 소수를 찾고, 찾은 소수로 슈퍼 소수를 찾는 함수이다.

 각 숫자의 배수는 소수가 아님을 이용하는 에라토스테네스의 체 알고리즘으로 소수를 찾았다. 예제를 보면 답으로 나올 수 있는 최댓값인 3000번째 슈퍼 소수의 값을 알 수 있다. 이를 통해 배열의 크기를 정했다.