[BOJ] 1644 소수의 연속합

입력값의 최대 범위가 4,000,000이므로 숫자 하나하나 소수 판정을 하였다가는 시간초과가 날 것이 분명하므로 에라토스테네스의 채를 이용해 입력받은 수 범위 이내의 소수들을 배열에 저장해놓고 그 값들과 포인터 두 개로 더했다 뺐다를 반복해주며 n과 같은 경우가 발생한 횟수를 기록해주기만 하면 되는 문제일 것입니다.

prime=[1 for i in range(n+1)] # n까지 수의 범위
for i in range(2,int(n**0.5)+1): # 소수 판정을 위해 사용할 수의 범위 sqrt(n)
    if prime[i]==1:
        for j in range(i*2,n+1,i): # i 의 배수들 지워나가기
            prime[j]=0
prime=[i for i in range(2,n+1) if prime[i]==1]

이렇게 입력받은 범위 내의 소수들을 가지고있는 배열을 얻어줬습니다.

그리고 그 배열과 두 개의 포인터를 활용해서 코드를 짜 줍니다.

cnt=0 # n과 같은 횟수 저장
l,r=0,0 # 투 포인터?
total=0 # 합 저장

while ==len(prime): # 포인터중 작은 값이 최댓값이 될 경우?
    if total==n: # 합이 n인 경우
        cnt+=1
    if total<n: # 합이 n보다 작은 경우
        if r<len(prime): # 만들어놓은 소수의 범위 안에 r이 존재하는 경우
            total+=prime[r]
            r+=1
        else: # r이 만들어놓은 소수 중 가장 큰 값을 가졌었는데 그보다 큰 수를 요구하는 경우
            break
    else:
        total-=prime[l]
        l+=1

print(cnt)

총 코드

n=int(input())
p=[1 for i in range(n+1)]
for i in range(2,int(n**0.5)+1):
    if p[i]==1:
        for j in range(i*2,n+1,i):
            p[j]=0
p=[i for i in range(2,n+1) if p[i]==1]
cnt=0
l,r=0,0
t=0
while l<len(p):
    if t==n:
        cnt+=1
    if t<n:
        if r<len(p):
            t+=p[r]
            r+=1
        else:
            break
    else:
        t-=p[l]
        l+=1
print(cnt)