BOJ 3896 : 소수 사이 수열

• 문제 링크 : boj.kr/3896
• 난이도 : S1
• 태그 : 에라토스테네스의 체, 이분 탐색

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

vector<int> get_primes(int n) {
    vector<int> prime;
    vector<int> sieve(n+1);
    for(int i = 2; i <= n; i++) {
        if(sieve[i]) continue;
        prime.emplace_back(i);
        for(int j = i+i; j <= n; j += i) {
            sieve[j] = 1;
        }
    }
    return prime;
}

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

    vector<int> arr = get_primes(1299709);

    int T;
    cin >> T;
    while(T--) {
        int k;
        cin >> k;
        int a = *lower_bound(all(arr), k);
        if(a == k) {
            cout << "0\n";
            continue;
        }
        int b = *(lower_bound(all(arr), k)-1);
        cout << a - b << "\n";
    }

    return 0;
}

---

풀이

구해야 하는 것을 다시 쓰면 (k보다 크거나 같은 가장 작은 소수 A) - (k보다 작거나 같은 가장 큰 소수 B)이다.

에라토스테네스의 체를 이용하여 범위 내의 소수 목록을 구하고, 이분탐색을 이용하여 A를 구해준다.

A가 만약 k와 같다면, 결과는 0이 된다.

아니라면 A 직전의 소수가 B가 된다.