📚 1644 - 소수의 연속합

소수의 연속합

이해

투 포인터 문제를 많이 풀어본 사람들은 금방 해결할 문제이다!

✏️ 투 포인터 특징
arr 배열이 있을 때
start : 배열에서 검토 시작점
end : 배열에서 검토 끝점

start과 end 사이를 검토해가며, 연속된 소수의 합이 몇 가지인지 구하면 된다!

추가로, 소수 구하는 반복문을 통해 소수들을 구하면 된다.

소스

import sys

# INF = 4000010

read = sys.stdin.readline

n = int(read())

if n == 1:
    print(0)
    sys.exit()

decimal = []
decimalCheck = [False] * (n+1)


def decimalFun():
    for i in range(2, n+1):
        if not decimalCheck[i]:
            decimal.append(i)
            for j in range(i + i, n+1, i):
                decimalCheck[j] = True

# 소수
decimalFun()

start = 0
end = 0
permission = decimal[0]

cnt = 0

while True:
    if permission == n:
        cnt += 1

    if permission >= n:
        permission -= decimal[start]
        start += 1
    else:
        end += 1

        if end == len(decimal) or decimal[end] > n:
            break
        permission += decimal[end]

print(cnt)