[백준] 1644번 소수의 연속합

💡문제접근

• 에라토스테네스의 체와 슬라이싱을 이용해서 구할 수 있었다.

💡코드(메모리 : 73980KB, 시간 : 1632ms)

import sys
input = sys.stdin.readline

N = int(input())
prime_number = []
arr = [True] * (N+1)
arr[0] = False
arr[1] = False
for i in range(2, N+1):
    if arr[i]:
        prime_number.append(i)
        for j in range(i*i, N+1, i):
            arr[j] = False

cnt = 0
start = 0
end = 0
while end <= len(prime_number):
    if sum(prime_number[start:end+1]) == N:
        cnt += 1
        start += 1
        end += 1
    elif sum(prime_number[start:end+1]) > N:
        start += 1
    else:
        end += 1
print(cnt)

💡소요시간 : 17m