[BAKJOON] #3896. 소수 사이 수열 (이진 탐색)

BAKJOON #3896. 소수 사이 수열 문제를 파헤쳐보자 :)

Chang Hyewon

Aug 11, 2025

알고리즘 Bakjoon

TABLE OF CONTENTS

1. 문제 설명

📌

연속한 소수 p와 p+n이 있을 때, 그 사이에 있는 n-1개의 합성수(소수나 1이 아닌 양의 정수)는 길이가 n인 소수 사이 수열라고 부른다.

양의 정수 k가 주어졌을 때, k를 포함하는 소수 사이 수열의 길이를 구하는 프로그램을 작성하시오. k를 포함하는 소수 사이 수열이 없을 때는 길이가 0이다.

예를 들어, 소수 23과 29의 소수 사이 수열은 {24, 25, 26, 27, 28}이고, 길이는 6이다.

2. 입출력 설명

2-1. 입력

📌

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 테스트 케이스는 한 줄로 이루어져 있고, 한 줄에 정수 k가 주어진다. 각각의 정수는 1보다 크고, 100000번째 소수(1299709)와 작거나 같다.

2-2. 출력

📌

각각의 테스트 케이스에 대해서 k가 합성수라면 k를 포함하는 소수 사이 수열의 길이를 출력한다. 그렇지 않으면 0을 출력한다.

3. 문제 풀이


import sys
import bisect

def solve():
    input = sys.stdin.readline
    MAX = 1_299_709
    sieve = [True] * (MAX + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(MAX**0.5) + 1):
        if sieve[i]:
            for j in range(i * i, MAX + 1, i):
                sieve[j] = False

    primes = [i for i, is_p in enumerate(sieve) if is_p]

    T = int(input())
    for _ in range(T):
        k = int(input())
        if sieve[k]:
            print(0)
        else:
            idx = bisect.bisect_left(primes, k)
            # primes[idx]는 k보다 크거나 같은 첫 소수
            smaller = primes[idx-1]
            larger = primes[idx]
            print(larger - smaller)

if __name__ == "__main__":
    solve()