백준_1644_소수의 연속합

문제

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

1644번: 소수의 연속합

풀이

2부터 N까지의 소수를 구하고, Two Pointer 을 이용해서, 합이 N이 되는 경우를 찾는다.

 

1) 에라토스테네스의 체

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

2) 투 포인터

시작 인덱스와 끝 인덱스를 옮겨가면서, 누적합을 구한다.

코드

N = int(input())

# Get Prime
primes = list()
numBoard = [1, ]*(N+1)
primeList = list()

for factor in range(2, len(numBoard)) : 
    if numBoard[factor] == 0 : continue
    for i in range(2*factor, len(numBoard), factor) : 
        numBoard[i] = 0

for factor in range(2, len(numBoard)) : 
    if numBoard[factor] == 1 : 
        primeList.append(factor)
    
# Get Sum - two pointer
s, e, ans = 0, 1, 0

if primeList : 
    accumulate = primeList[s]
    
    while s<e :     
        if accumulate==N : 
            ans += 1
        
        if accumulate>=N :
            accumulate -= primeList[s]
            s += 1
            
        elif accumulate<N : 
            if e == len(primeList) : break
            accumulate += primeList[e]
            e += 1

print(ans)