[Python] 백준 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. 에라토스테네스의 체 알고리즘을 이용해 2 ~ n + 1의 구간에서 소수를 저장한 리스트를 만든다.

2. l, r = 0, 0 으로 하는 투 포인터 알고리즘을 만든다.

 

1) Sum에 각 원소들의 부분합을 저장하고, l 은 Sum이 클 때 빼주는 역할, r 은 Sum 이 작을 때 키우는 역할이다.

2) Sum 과 n 이 같을 때마다 cnt 를 증가시킨다.

 

 

import sys
input = sys.stdin.readline

n = int(input())
def prime(n):
	d = [False, False] + [True] * (n-1)
	primes = []
	for i in range(2, n+1):
		if d[i]:
			primes.append(i)
			for j in range(i*2, n+1, i):
				d[j] = False
	return primes

primes = prime(n)+[0]
Sum, cnt = 0, 0
l, r = 0, 0
while True:
	if r == len(primes):
		break
	if Sum == n:
		cnt += 1
		Sum -= primes[l]
		l += 1
	else:
		if Sum < n:
			Sum += primes[r]
			r += 1
		else:
			Sum -= primes[l]
			l += 1
print(cnt)