[백준] 소수의 연속합

출처::  www.acmicpc.net/problem/1644

분류:: 에라토스테네스의 체, 투포인터 

 

1. 문제 이해 및 해결과정

- n이 400만으로 일반적인 소수찾는 알고리즘으로 탐색이 안된다 -> 에라토스테네스의 체 이용해야한다. - 1. 에라토스테네스의 체로 가능한 소수를 찾고 - 2. 투포인터로 연속된 소수의 합 가능한 경우를 센다

cf) 

에라토스테네스의 체 hiruby.tistory.com/463

투포인터 hiruby.tistory.com/416

 

2. 풀이방법

#소수의 연속합
#https://www.acmicpc.net/problem/1644
import sys
import math
sys.stdin = open("input.txt","r")
n=int(input())
arr=[True for _ in range(n+1)]
prime=[]

#2부터 n까지 중 가능한 소수 찾기
def isprime(n):
    for i in range(2,int(math.sqrt(n))+1):
        if arr[i]==True:
            j=2
            while i*j<=n:
                arr[i*j]=False
                j+=1
isprime(n)
for i in range(2,n+1):
    if arr[i]:
        prime.append(i)

#투포인터
s,e=0,0
sum=0
cnt=0
for s in range(len(prime)):
    while e<len(prime) and sum<n: #합이 목표값보다 작고, 인덱스 이내라면
        sum+=prime[e] #sum늘림
        e+=1
    if sum==n: #연속된 소수의 합이 n이라면
        cnt+=1
    sum-=prime[s]
print(cnt)

 

 

3. 오답원인

 

4. 알게된 점