[백준] 소수의 연속합

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

에라토스테네스의 체와 누적합을 활용하는 문제입니다. 먼저, 에라토스테네스의 체를 통해 n보다 작은 모든 소수를 구해줍니다. 그 다음 소수들을 누적합을 해가면서 check라는 set에 저장을 해줍니다. 현재까지의 누적합을 저장하면서 동시에 현재까지의 누적합에 n을 뺐을 때의 값이 check set에 들어있다면 연속된 소수의 합으로 만들 수 있는 경우가 됩니다.

 

import sys

input = sys.stdin.readline

n = int(input())
check = set()

def era(num):
    isPrime = [True for _ in range(n + 1)]
    p = 2

    while p * p <= num:
        # p가 소수인 경우 배수를 모두 제거한다.
        if isPrime[p]:
            for i in range(p * p, num + 1, p):
                isPrime[i] = False

        p += 1

    nums = []

    for i in range(2, num + 1):
        if isPrime[i]:
            nums.append(i)

    return nums

primes = era(n)

cumulated_sum = 0
ans = 0

for p in primes:
    # 현재까지의 소수의 합
    cumulated_sum += p
    check.add(cumulated_sum)

    if cumulated_sum == n:
        ans += 1
    # 현재까지의 합과의 차이가 n인 누적합이 존재한다면 연속합을 만들 수 있다.
    if cumulated_sum - n in check:
        ans += 1

print(ans)