BOJ 3896 - 소수 사이 수열 링크
(2023.09.25 기준 S1)

문제

주어지는 k가 소수이면 0, 합성수이면 k를 포함하는 연속하는 두 소수의 차 출력

알고리즘

주어지는 수의 최대가 1,299,709이므로 에라토스테네스의 체를 이용하여 소수 판정. 그리고 인접한 소수를 빠르게 찾기 위한 이분 탐색

풀이

에라토스테네스의 체의 시간 복잡도는 O(N log log N) 이므로 130만 가까이는 아주 충분히 돌리고도 남는다.

소수 사이 수열의 길이는 합성수의 개수 + 1. 즉, 두 소수의 차와 같다.
주어지는 k가 소수인지 판별 및 k와 인접한 소수를 최대한 빠르게 구해야 하므로, 소수인지 판별할 130만 길이의 bool 배열 및 100,000번째 소수까지 담겨져 있는 리스트가 필요하다. 그러므로 에라토스테네스의 체를 돌릴 때, 각 수가 소수이면 따로 소수 리스트에 담아주자.

그리고 주어지는 k가 합성수이면 소수 리스트에서 이분 탐색을 하여 빠르게 연속하는 두 소수를 찾아 두 소수의 차를 출력하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAX = 1299710;

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

    // sieve
    bool is_prime[MAX]; fill(is_prime + 2, is_prime + MAX, true);
    vector<int> primes;
    for (int i = 2; i < MAX; i++) if (is_prime[i]){
        primes.push_back(i);
        for (ll j = (ll)i * i; j < MAX; j += i) is_prime[j] = false;
    }

    int T, k; cin >> T;
    while (T--){
        cin >> k;

        // 소수면 0 출력
        if (is_prime[k]) cout << 0 << '\n';

        // 합성수면 k를 포함하는 연속하는 두 소수의 차 출력
        else{
            int idx = lower_bound(primes.begin(), primes.end(), k) - primes.begin();
            cout << primes[idx] - primes[idx - 1] << '\n';
        }
    }
}

• Python

import sys; input = sys.stdin.readline
from bisect import bisect

# sieve
MAX = 1299710
is_prime = [True] * MAX
primes = []
for i in range(2, MAX):
    if is_prime[i]:
        primes.append(i)
        for j in range(i ** 2, MAX, i):
            is_prime[j] = False

for _ in range(int(input())):
    k = int(input())

    # 소수면 0 출력
    if is_prime[k]:
        print(0)

    # 합성수면 k를 포함하는 연속하는 두 소수의 차 출력
    else:
        idx = bisect(primes, k)
        print(primes[idx] - primes[idx - 1])