백준 1644

문제

---

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

• 3 : 3 (한 가지)
• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

 

 

입력

---

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

 

 

 

출력

---

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

몇 가지 자연수의 예를 들어 보면 다음과 같다.

 

예 )

1. 3 : 3 (한 가지)
2. 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
3. 53 : 5+7+11+13+17 = 53 (두 가지)

접근법은

1. 에라토스테네스의 체로 먼저 소수를 구한다음 리스트로 나열하여,  밑의 코드에서는 primes
2. 그중에서 투포인터(Two_Pointer) 기법으로 합을 표시하여 구해주면 간단히 구현 가능하겠다.

 

코드구현

---

n = int(input())
check =[False]*(n+1)
#소수들을 넣어 놓는 박스
primes = []
for i in range(2,n+1):
    #이미 소수가 아니면 skip
    if check[i]==True: continue
    j=i*2
    #j가 check 가 안되어있으면, 소수라는 의미이니 Primes에 추가
    primes.append(i)
    while j<=n:
        check[j]=True
        j+=i

left =0
right = 0
sum_of_prime=0 if len(primes)==0 else primes[0]
cnt = 0

#투 포인터로 접근하여, 소수의 연속합을 세어준다.
while left<=right and right<len(primes):
    if sum_of_prime <= n :
        if sum_of_prime == n:
            cnt += 1
        right += 1
        if right < len(primes):
            sum_of_prime += primes[right]
    else:
        sum_of_prime-=primes[left]
        left+=1

print(cnt)