<투포인터> 1644번 소수의 연속합 with 파이썬

 

문제

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

• 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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

정답비율

42.548%

알고리즘 분류

 #수학 #정수론 #투포인터 #소수 #에라토스테네스의체

 

import sys
input = sys.stdin.readline

n = int(input())
prime_bool = [True] * (n+1)
prime_bool[0], prime_bool[1] = False, False
for i in range(2, int(n**1/2) + 1):
    if prime_bool[i]:
        j = 2
        while i * j <= n:
            prime_bool[i * j] = False
            j += 1
prime_lst = []
# 소수 리스트 만들기
for i in range(2, n+1):
    if prime_bool[i]:
        prime_lst.append(i)
# [2, 3, 5, 7, 11, 13, 17, 19]

# 투포인터 이용해서 합이 n인 경우 세기
count = 0
end = 0
interval_sum = 0
for start in range(0, len(prime_lst)):
    while interval_sum < n and end < len(prime_lst):
        interval_sum += prime_lst[end]
        end += 1
    if interval_sum == n:
        count += 1
    interval_sum -= prime_lst[start]
print(count)

 

 - 에라토스 테네스의 체 기본문제와 투 포인터 기본 문제를 순서대로 나열한 문제 느낌이다.

 

 - 먼저 에라토스테네스의 체를 이용해서 n보다 작거나 같은 소수리스트를 만들었다.

 

 - 소수리스트를 투포인터를 이용해서 연속합이 n이 되는 것을 카운팅하여 출력했다.

 

 

---

 

 

 

 

참고

 

1644번: 소수의 연속합