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

문제

 

풀이

에라토스테네스의 체, 두 포인터를 사용해 풀면 된다.

구간 합은 선택사항..ㅎㅎ

 

나동빈님의 강의에 전부 정리되어있다.

https://www.youtube.com/watch?v=cswJ1h-How0&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=9 

 

코드

import sys, math
input = sys.stdin.readline

n = int(input())
intervalSum = [0]
isPrimeList = [True for _ in range(n + 1)]

for i in range(2, int(math.sqrt(n)) + 1):
    if isPrimeList[i]:
        for j in range(i * 2, n + 1, i):
            isPrimeList[j] = False

primeNumList = [i for i in range(2, n + 1) if isPrimeList[i]]

tempSum = 0
for prime in primeNumList:
    tempSum += prime
    intervalSum.append(tempSum)

cnt = 0
start = end = 1

while start < len(intervalSum) and end < len(intervalSum):
    if intervalSum[end] - intervalSum[start - 1] == n:
        cnt += 1
        start += 1
    elif intervalSum[end] - intervalSum[start - 1] < n:
        end += 1
    else:
        start += 1

print(cnt)

 

마무리

에라토스테네스의 체, 구간 합 등 오랜만에 써본 알고리즘이 많았다.