1644_소수의 연속합

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

 

 

이전에 소수구하기 문제를 풀었던 경험이 있는데 소수를 구하는 리스트를 만든 후에, 저번문제에서 다뤘던 방식을 사용해서 문제를 풀면 된다.

 

두가지의 문제가 합쳐진 형태이다.

 

n = int(input())
lst = [True] * (n+1)

for i in range(2,int((n+1)**0.5)+1):
    if lst[i]:
        for j in range(i*2,n+1,i):
            lst[j] = False
sosu = [0]
for i in range(2,n+1):
    if lst[i]:
        sosu.append(i)

start,end = 0,0
SUM,cnt,LEN = 0,0,len(sosu)

while start < LEN:
    if SUM <= n:
        if SUM ==n:
            cnt +=1
        if end < LEN-1:
            end +=1
            SUM += sosu[end]
        else:
            break
    else:
        SUM -= sosu[start]
        start +=1

print(cnt)