백준 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

20

예제 출력 1

0

예제 입력 2

3

예제 출력 2

1

예제 입력 3

41

예제 출력 3

3

예제 출력 4

53

예제 출력 4

2

제출 답안

import math
import sys
input = sys.stdin.readline

m = 4000001
n = int(input())
array = [True for i in range(m + 1)] 
min_num = 0
graph = []

for i in range(2, m): 
    if array[i] == True: 
        j = 2 
        graph.append(i)
        while i * j <= m:
            array[i * j] = False
            j += 1

count = 0
interval_sum = 0
end = 0

for start in range(len(graph)):
    if graph[start] <= n:
        while interval_sum < n and end < len(graph):
            interval_sum += graph[end]
            end += 1
        if interval_sum == n:
            count += 1
        interval_sum -= graph[start]
    else:
        break
print(count)

1. 최대 4,000,000까지 구하는 것이여서 4,000,001까지 소수를 구한다.
   1. 이번에는 소수인 것들만 리스트에 담는다.
2. 투포인트로 시간을 줄인다.
3. 우선 graph에 있는 소수가 n보다 작으면 while문을 돌려서 계속 값을 더한다.
   1. 마지막 끝점이 소수의 총 갯수보다 작고 n보다 작을때까지 end를 늘려나간다.
4. 그 다음에 빠져나와서 계속 누적된 값이 n이랑 같으면 count에 1을 더한다.
5. 그 다음에 맨 앞 즉, 처음 스타트인 소수를 빼서 0번째 값을 줄여나간다.

print를 추가해서 돌려본 결과

import math
import sys
input = sys.stdin.readline

m = 4000001
n = int(input())
array = [True for i in range(m + 1)]
min_num = 0
graph = []

for i in range(2, m):
    if array[i] == True:
        j = 2
        graph.append(i)
        while i * j <= m:
            array[i * j] = False
            j += 1

count = 0
interval_sum = 0
end = 0

# start를 차례대로 증가시키며 반복
for start in range(len(graph)):
    print(f'graph[start]:{graph[start]}')
    if graph[start] <= n:
    # end를 가능한 만큼 이동시키기
        while interval_sum < n and end < len(graph):
            print(f'interval_sum:{interval_sum}, graph[end]:{graph[end]}')
            interval_sum += graph[end]
            end += 1
    # 부분합이 m일 때 카운트 증가
        if interval_sum == n:
            count += 1
        interval_sum -= graph[start]
        print(f'interval_sum:{interval_sum}')
    else:
        break
print(count)

출력 결과

41
graph[start]:2
interval_sum:0, graph[end]:2
interval_sum:2, graph[end]:3
interval_sum:5, graph[end]:5
interval_sum:10, graph[end]:7
interval_sum:17, graph[end]:11
interval_sum:28, graph[end]:13
interval_sum:39
graph[start]:3
interval_sum:39, graph[end]:17
interval_sum:53
graph[start]:5
interval_sum:48
graph[start]:7
interval_sum:41
graph[start]:11
interval_sum:30
graph[start]:13
interval_sum:30, graph[end]:19
interval_sum:36
graph[start]:17
interval_sum:36, graph[end]:23
interval_sum:42
graph[start]:19
interval_sum:23
graph[start]:23
interval_sum:23, graph[end]:29
interval_sum:29
graph[start]:29
interval_sum:29, graph[end]:31
interval_sum:31
graph[start]:31
interval_sum:31, graph[end]:37
interval_sum:37
graph[start]:37
interval_sum:37, graph[end]:41
interval_sum:41
graph[start]:41
interval_sum:0
graph[start]:43
3

Process finished with exit code 0

• end까지 더해서 앞에서 부터 빼고있는것을 볼 수 있다.