[PS] BOJ 1644 / 소수의 연속합

Minjun Kim

11 Aug 2025 • 2 min read

문제 링크: https://www.acmicpc.net/problem/1644

Thumbnail: Photo by Ryunosuke Kikuno (Unsplash)

풀이

에라토스테네스의 체를 사용해 $N$까지의 소수를 미리 구하고, 소수들의 배열을 가지고 투 포인터 탐색을 활용해 연속 합을 구하면 됩니다.

에라토스테네스의 체

에라토스테네스의 체는 잘 알려진 소수 판별법으로, 1부터 $N$까지의 범위 안에서 소수를 일괄적으로 구할 때 사용합니다.

이번 문제에서는 에라토스테네스의 체로 소수를 판별한 뒤, 발견한 소수를 다시 배열에 저장합니다. 이후 소수의 연속 합을 계산하기 위해선 소수의 배열이 필요하기 때문입니다.

동시에, 소수를 판별하면서 누적합 배열도 계산했습니다. 하지만, 후술할 투 포인터 탐색을 생각하면 사실 굳이 누적합을 만들지 않고도 적절하게 구현할 수 있습니다.

N = int(input())

primes_acc = [0, ]
sieve = [True] * 4_000_001
sieve[0] = sieve[1] = False

for i in range(2, 2_001): # sqrt(4_000_000) = 2000
    if sieve[i]:
        j = i * 2
        while j <= 4_000_000:
            sieve[j] = False
            j += i
for i in range(4_000_001):
    if sieve[i]:
        primes_acc.append(primes_acc[-1] + i)
primes_cnt = len(primes_acc)

에라토스테네스의 체

투 포인터 탐색

투 포인터 탐색으로, 소수의 누적 합을 계산합니다. start를 기준으로, end를 1씩 늘려가면서 합이 N보다 크거나 같아지는 순간을 찾으면 됩니다.

cnt = 0
for start in range(primes_cnt):
    end = start + 1
    while end < primes_cnt:
        total = primes_acc[end] - primes_acc[start]
        if total > N:
            break
        elif total == N:
            cnt += 1
            break
        end += 1

print(cnt)

투 포인터 탐색

전체 코드

input = open(0).readline
N = int(input())

primes_acc = [0, ]
sieve = [True] * 4_000_001
sieve[0] = sieve[1] = False

for i in range(2, 2_001): # sqrt(4_000_000) = 2000
    if sieve[i]:
        j = i * 2
        while j <= 4_000_000:
            sieve[j] = False
            j += i
for i in range(4_000_001):
    if sieve[i]:
        primes_acc.append(primes_acc[-1] + i)
primes_cnt = len(primes_acc)

cnt = 0
for start in range(primes_cnt):
    end = start + 1
    while end < primes_cnt:
        total = primes_acc[end] - primes_acc[start]
        if total > N:
            break
        elif total == N:
            cnt += 1
            break
        end += 1

print(cnt)

solution.py