[백준, BOJ] 1644 - 소수의 연속합

1. Question

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

• 3 : 3 (한 가지)
• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

1.1 Input

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

1.2 Output

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

1.3 Example

입력	출력
20	0
3	1
41	3
53	2

2. Approach

에라토스테네스의 체를 이용하여 소수 리스트를 만들고 거기에 투 포인터를 적용하는 문제이다. 입력중에 1이 있으니 주의 하도록한다. 또한 백준 서버 머신은 exit 함수의 인자가 0이 아니면 항상 런타임 에러가 나므로 주의!

3. Submission

4. Code

import sys
import math
rl = sys.stdin.readline
    
def getPrimes(n):
    is_prime = [False, False] + [True] * n
    max_len = int(math.sqrt(n))
    
    for i in range(2, max_len):
        if is_prime[i]:
            for j in range(2*i, n+1, i):
                is_prime[j] = False
    
    return [i for i in range(2, n+1) if is_prime[i]]

N = int(rl())

if N == 1:
    print(0)
    exit(0)

p_range = getPrimes(N)
p1 = 0
p2 = 0
ans = 0
s = p_range[0]
while not((p2 == (len(p_range) - 1)) and s < N):
    if s == N:
        ans += 1
        s -= p_range[p1]
        p1 += 1
    elif s < N:
        p2 += 1
        s += p_range[p2]
    else:
        s -= p_range[p1]
        p1 += 1
print(ans)