[백준]소수의 연속합

1. 풀이

(1) 에라토스테네스의 체를 이용하여 모든 소수를 찾고

(2) 투포인터를 이용하여 합이 N이되는 경우의 수를 찾으면 된다.

​

* 투포인터 : 시작부분s와 끝부분e, [s,e)까지의 합 S라 할때, (시간복잡도는 O(n))

(이때 L의 각 원소는 양수이고, N도 양수여야 한다)

i) S==N이면

cnt+=1, e+=1(e가 범위밖(==size+1)이면 끝내기), S+=L[e-1]

ii) S<N이면

e+=1(e가 범위밖(==size+1)이면 끝내기), S+=L[e-1]

iii) S>N이면

S-=L[s], s+=1

​

2. 소스코드

N=int(input())

isPrime=[1 for i in range(N+1)]
isPrime[0]=isPrime[1]=0
primeL=[]
def aratos():
    for i in range(2,N+1):
        if isPrime[i]:
            primeL.append(i)
            for j in range(i*i,N+1,i):
                isPrime[j]=0

def twoPoint():
    s=0
    e=0
    cnt=0
    S=0
    while(1):
        if S==N:
            cnt+=1
            e+=1
            if e==size+1:
                return cnt
            S+=primeL[e-1]
        elif S<N:
            e+=1
            if e==size+1:
                return cnt
            S+=primeL[e-1]
        else:
            S-=primeL[s]
            s+=1


aratos()
size=len(primeL)
print(twoPoint())