Baekjoon 1644. 소수의 연속합 / Python

알고리즘 설명

문제 설명

자연수 n 이 주어질 때, n을 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제

코드 설명

1. n이하의 모든 소수를 찾는다. (에라토스테네스의 체를 이용)
2. 찾은 소수들을 투 포인터를 이용하여 연속된 소수의 합으로 n을 나타낼 수 있는 경우를 찾는다.

import math
n = int(input())

# n이 1인 경우 소수의 합으로 나타낼 수 없으므로 0 출력 후 종료
if n == 1:
    print(0)
    exit(0)

# 에라토스테네스의 체 초기화
arr = [1] * (n + 1)
arr[0] = arr[1] = 0  # 0과 1은 소수가 아니므로 0으로 설정

# 에라토스테네스의 체를 사용하여 소수 판별
for i in range(2, int(n**0.5) + 1):
    if arr[i] == 1:
        for j in range(i * i, n + 1, i):
            arr[j] = 0

# 소수 리스트 생성
prime_list = [i for i in range(2, n + 1) if arr[i] == 1]

# 투 포인터를 사용하여 연속된 소수의 합으로 n을 나타낼 수 있는 경우의 수를 찾기
s = 0
e = 0
res = 0
tmp = prime_list[0]

while s <= e:
    if tmp < n:
        e += 1
        if e == len(prime_list):
            break
        tmp += prime_list[e]
    elif tmp > n:
        tmp -= prime_list[s]
        s += 1
    else:
        res += 1
        e += 1
        if e == len(prime_list):
            break
        tmp += prime_list[e]

print(res)