백준 3896 : 소수 사이 순열

www.acmicpc.net/problem/3896

3896번: 소수 사이 수열

어떠한 정수 n이 주어졌을 때 (n보다 큰 소수 중 가장 작은 값 - n보다 작은 소수 중 가장 큰 값)을 구하는 문제이다.

최대 100000번째 소수까지 주어지므로 소수 판별을 위하여 에라토스테네스의 체를 사용하였다. 에라토스테네스의 체는 아래 움짤처럼 소수의 배수들을 체에 거르듯이 걸러주고 나면 남은 수가 소수가 되는 방법이다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

먼저 소수를 다 구해주고 n값을 입력받아서 (upper_bound 인덱스의 값 - (lower_bound - 1번째 인덱스의 값))을 계산해주었다. 소수를 구할 때는 bitset을 이용하여 메모리를 아꼈고 체크되지 않은 비트의 인덱스만 소수 배열에 추가해주었다.

#include <iostream>
#include <bitset>
#include <cmath>
#include <algorithm>

#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX_PRIME 1299710
#define BOUNDARY prime_num, prime_num + 100000, n
using namespace std;

bitset<MAX_PRIME> bs;
int prime_num[100000];

void sieve() {
	int idx = 0;
	int max_idx = sqrt(MAX_PRIME);
	for (int i = 2; i <= max_idx; i++) {
		if (bs[i]) continue;
		for (int j = 2 * i; j < MAX_PRIME; j += i) bs.set(j, 1);
	}
	for (int i = 2; i < MAX_PRIME; i++) {
		if (!bs[i]) prime_num[idx++] = i;
	}
}

int main() {
	fastio;
	int t, n;
	sieve();
	cin >> t;
	while (t--) {
		cin >> n;
		if (prime_num[lower_bound(BOUNDARY) - prime_num] == n) {
			cout << 0 << '\n'; continue;
		}
		cout << prime_num[upper_bound(BOUNDARY) - prime_num] - prime_num[(lower_bound(BOUNDARY) - prime_num) - 1] << '\n';
	}

	return 0;
}

메모리: 2564 KB

시간: 4 ms