[백준 1644] 소수의 연속합(Python)

1. 아이디어

먼저 소수들을 에라토스테네스로 찾는다. 그리고 1번째 피연산자를 바꿔가며, 연속적으로 더해본다.(사용되는 피연산자들은 모두 소수) 그리고 그 결과가 N과 같다면 경우의 수를 하나 추가한다. 연속적으로 소수를 더하는 과정에서 N을 넘어버리게 된다면, 연산을 중단한 후, 1번째 피연산자의 바로 다음 소수를 1번째 피연산자로 지정한다.

1번째 피연산자가 N을 넘길 때까지 위의 과정을 반복한다.

2. 코드

import sys

n = int(sys.stdin.readline().rstrip())
table = [True for _ in range(n+1)]
for i in range(2): table[i] = False

for i in range(2, n+1):
    if table[i]:
        for k in range(i+i, n+1, i):
            table[k] = False

ln = 0
answer = 0
while True:
    while ln < n+1 and not table[ln]: ln += 1
    if ln == n+1: break
    ok = False
    total = 0

    for i in range(ln, n+1):
        if table[i]: total += i
        if total >= n:
            if total == n: ok = True
            break
    
    if ok: answer += 1
    ln += 1

print(answer)