[백준] 1644번: 소수의 연속합 (에라토스테네스의 체, 투 포인터)

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

1644번: 소수의 연속합

이 문제는 에라토스테네스의 체 + 투 포인터 문제이다!

전에 풀었던 문제들의 알고리즘 두 개를 섞어 놓은 문제라 신기했다.

급하게 풀어서 코드가 깔끔하지는 않지만 통과하였기 때문에 일단 코드를 올려보겠다.

 

파이썬 풀이

import math
n = int(input())
arr = [False, False] + [True for i in range(n-1)]
for i in range(2, int(math.sqrt(n)+1)):
    if arr[i]:
        for k in range(i + i, n+1, i):
            arr[k] = False
prime_list = []
for i in range(len(arr)):
    if arr[i]:
        prime_list.append(i)
cnt = 0
interval_sum = 0
end = 0
for start in range(len(prime_list)):
    while interval_sum < n and end < len(prime_list):
        interval_sum += prime_list[end]
        end += 1
    if interval_sum == n:
        cnt += 1
    interval_sum -= prime_list[start]

print(cnt)