BOJ 1644 - 소수의 연속합

문제

백준 온라인 저지 - 1644번

풀이 과정

N 이 주어질 때 연속된 소수의 합으로 N 을 만족시킬 수 있는 경우의 수를 찾는 문제입니다.

특정 수들의 합이 N 이 되기 위해서는 해당 수들이 N 보다 작아야 함은 자명합니다.
따라서 N 보다 작거나 같은 수들 중 모든 소수를 에라토스테네스의 체 를 이용해 먼저 구해놓은 다음 연속된 구간을 찾으면 됩니다.
N 의 최대 값이 크기 때문에 O(N^2) 으로 모든 합의 경우의 수를 따지면 시간 초과가 발생합니다.

코드

N = int(input())


def eratos(n):
    sieve = [1] * (n + 1)

    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i]:
            for j in range(i * 2, n + 1, i):
                sieve[j] = 0

    return [i for i in range(2, n + 1) if sieve[i]]


def solution():
    primes = eratos(N)

    if not primes:
        return 0

    answer = 0
    head, tail = 0, 0
    acc = primes[0]

    while head <= tail:
        if acc < N:
            tail += 1
            if tail < len(primes):
                acc += primes[tail]
            else:
                break
        else:
            if acc == N:
                answer += 1
            acc -= primes[head]
            head += 1

    return answer


print(solution())