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

문제

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

---

풀이

먼저 소수를 찾는 방법은 에라토스테네스의 체 방법으로 찾을 수 있다.
2부터 자신이 현재까지 나눠지지 않아 True(소수)라면, 해당 수를 소수 리스트에 넣고 그의 배수를 False(소수가 아님)으로 바꿔준다.
이후 소수들에 대해 투포인터를 활용해 연속된 수의 합을 구해본다.
연속된 수의 합이 원하는 수라면 count를 하나씩 늘려 값을 찾는다.

---

코드

N = int(input())

eratos = [False, False] + [True]*(N-1)
primes = []

for i in range(2,N+1):
    if eratos[i]:
        primes.append(i)
        for j in range(2*i, N+1, i):
            eratos[j] = False

answer = 0
s,e = 0,0
while e <= len(primes):
    temp = sum(primes[s:e])
    if temp == N:
        answer += 1
        s += 1
    elif temp < N: e += 1
    else: s += 1

print(answer)