[BOJ, Python] 1644 - 소수의 연속합 ( with 에라토스테네스의 체, 투 포인터 )

 

1644번: 소수의 연속합

자연수 N이 주어졌을 때, N보다 작은 연속하는 소수들의 합이 N과 같을 경우의 수를 구하는 문제이다. N의 최댓값이 4,000,000이므로, 소수 판별에 있어서는 에라토스테네스의 체를, 연속합은 투 포인터 알고리즘을 통해 시간복잡도 O(n)으로 구현하였다.

N = int(input())

# 예외 처리
if N == 1:
    print(0)
    exit(0)

# 소수 판별 by 에라토스테네스의 체
sosu = [True for _ in range(N + 1)]
number = list()
for i in range(2, N + 1):
    if sosu[i]:
        for j in range(i, N + 1, i):
            sosu[j] = False
        number.append(i)

# N과 마지막 값이 같으면 1개를 먹고 시작
ans = 1 if number[-1] == N else 0

# 뒤에서부터 투포인터 탐색
start = len(number) - 2
end = len(number) - 1
s = number[start] + number[end]

while 0 <= start < end < len(number):
    # 합이 값보다 크거나 같으면 연속 소수의 개수 유지
    # 시작점, 끝점 둘 다 이동
    if s >= N:
        # 같을 때만 +1
        if s == N:
            ans += 1
        start -= 1
        end -= 1
        s += number[start]
        s -= number[end + 1]
    # 아닐 때는 연속 소수의 개수 증가(end += 1)
    else:
        end += 1
        s += number[end]
print(ans)