취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3896번 문제인 소수 사이 수열이다.
문제는 아래 링크를 확인하자.

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

에라토스테네스의 체를 이용하여 10만개의 소수를 먼저 구해주자.

소수 사이 수열이 존재하지 않는 숫자들은 1과(1보다 작은 소수가 없기 때문) 소수들 뿐이라는 것을 관찰하자.

따라서 이 문제를 해결하려면 1 또는 소수가 입력으로 들어오면 0을 출력해주고 그렇지 않은 경우 주어진 수보다 큰 소수와 작은 소수의 차를 출력해주면 된다.

주어진 수보다 큰 소수와 작은 소수는 이분탐색(binary search)를 통해 빠르게 구할 수 있다.

아래는 제출한 소스코드이다.

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

vector<bool> sieve(1299710);
int prime[100000];

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

	int idx = 0;
	sieve[0] = 1;
	for (int i = 2; i < 1140; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j < 1299710; j += i) sieve[j] = 1;
	}

	for (int i = 2; i < 1299710; i++) {
		if (sieve[i]) continue;
		prime[idx++] = i;
	}

	int T; cin >> T;
	while (T--) {
		int x; cin >> x;
		if (!sieve[x]) cout << 0 << '\n';
		else {
			int l, r;
			
			int L = 0, R = 99999;
			while (L < R) {
				int mid = (L + R) / 2;
				if (x < prime[mid]) R = mid;
				else L = mid + 1;
			}
			r = R;

			L = 0, R = 99999;
			while (L < R) {
				int mid = (L + R) / 2 + 1;
				if (prime[mid] < x) L = mid;
				else R = mid - 1;
			}
			l = L;

			cout << prime[r] - prime[l] << '\n';
		}
	}
}