[Python] 백준(BOJ) 1644번: 소수의 연속합 - 소수, 투포인터 알고리즘

문제

1644번: 소수의 연속합

풀이

소수 찾기(yuuj.tistory.com/158) + 투포인터 알고리즘(yuuj.tistory.com/160)인 문제.

최소 소수는 2이기 때문에 인풋으로 1이 들어올 경우를 예외처리 안해주면 런타임에러가 난다.

import sys


# n까지의 소수 리턴
def prime(n):
    li = [False, False] + [True for _ in range(n-1)]
    p = []

    for i in range(len(li)):
        if li[i]:
            p.append(i)
            for k in range(i+i, len(li), i):
                li[k] = False
    return p


S = int(sys.stdin.readline())

# prime(1)은 빈 배열을 리턴하기 때문에 미리 예외처리
if S == 1:
    print(0)
else:
    arr = prime(S)

    start = 0
    end = 1
    count = 0
    sum = arr[start]
    if sum == S:
        count += 1

    while not (start == end == len(arr)):
        if sum < S and end < len(arr):
            sum += arr[end]
            end += 1
        else:
            sum -= arr[start]
            start += 1

        if sum == S:
            count += 1

    print(count)