[Python] 백준 #1644 소수의 연속합

📚문제: #1644 소수의 연속합(Gold 3)

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

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

예제 모음

input1 : 41, output1 : 3
input2 : 53, output2 : 2

아이디어 및 구현

• 에라토스테네스의 체 알고리즘으로 1 ~ N까지의 소수를 구한다.

import sys
import math

# 자연수 N이 주어집니다.
N = int(sys.stdin.readline().rstrip())

# 연속된 소수를 구하자(에라토스테네스의 체)
array = [True] * (N+1)

# 1은 소수가 아니다.
array[1] = False

# 소수 리스트
prime = []

for i in range(2, int(math.sqrt(N))+1):

    if array[i]:

        j = 2

        # 소수의 배수는 다 제거
        while i * j <= N:

            array[i*j] = False

            j += 1

• Two Pointers 알고리즘으로 연속된 소수의 구간 합이 N을 만족하는지 확인한다.

# 연속된 소수의 합으로 나타내는 것이 가능한지 확인
s = 0
e = 0

if N == 1:

    print(0)

else:

    # 소수의 합 초기화
    sum_of_prime = prime[0]

    # 경우의 수
    cnt = 0

    while True:

        # N으로 나타낼 수 있을 때
        if sum_of_prime == N:

            cnt += 1

            # 시작위치 값 뺀다
            sum_of_prime -= prime[s]

            # 시작위치 한칸 증가
            s += 1
        
        # N보다 작을 때 끝을 한칸 증가시키고 값을 더한다.
        elif sum_of_prime < N:

            if e == len(prime)-1:

                break
            
            e += 1
            
            sum_of_prime += prime[e]

        else: # sum_of_prime > N

            # 시작위치 값 뺀다
            sum_of_prime -= prime[s]

            # 시작위치 한칸 증가
            s += 1

    print(cnt)

전체 코드

import sys
import math

# 자연수 N이 주어집니다.
N = int(sys.stdin.readline().rstrip())

# 연속된 소수를 구하자(에라토스테네스의 체)
array = [True] * (N+1)

# 1은 소수가 아니다.
array[1] = False

# 소수 리스트
prime = []

for i in range(2, int(math.sqrt(N))+1):

    if array[i]:

        j = 2

        # 소수의 배수는 다 제거
        while i * j <= N:

            array[i*j] = False

            j += 1

# 소수 선별
for i in range(2, N+1):

    if array[i]:

        prime.append(i)

# 연속된 소수의 합으로 나타내는 것이 가능한지 확인
s = 0
e = 0

if N == 1:

    print(0)

else:

    # 소수의 합 초기화
    sum_of_prime = prime[0]

    # 경우의 수
    cnt = 0

    while True:

        # N으로 나타낼 수 있을 때
        if sum_of_prime == N:

            cnt += 1

            # 시작위치 값 뺀다
            sum_of_prime -= prime[s]

            # 시작위치 한칸 증가
            s += 1
        
        # N보다 작을 때 끝을 한칸 증가시키고 값을 더한다.
        elif sum_of_prime < N:

            if e == len(prime)-1:

                break
            
            e += 1
            
            sum_of_prime += prime[e]

        else: # sum_of_prime > N

            # 시작위치 값 뺀다
            sum_of_prime -= prime[s]

            # 시작위치 한칸 증가
            s += 1

    print(cnt)