백준 1644 : 소수의 연속합 (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

20

예제 출력 1

0

---

나의 풀이

• 자연수를 연속된 소수의 합으로 나타내야 하기 때문에 우선 자연수 범위 내의 소수 배열을 구하고 배열 중 연속합이 N인 구간 개수를 세면 되는 문제이다. 완전탐색으로 소수 배열을 구하고 연속합을 탐색하면 O(N^3) 시간복잡도를 가지게 된다. 그러나 자연수 N은 최대 4,000,000이고 2초의 시간 제한 조건이 존재하기에 4(10^18) > 2(10^8) 로 시간초과가 발생할 것이다.
• 그렇다면 시간복잡도를 절감할 아이디어로 무엇이 적합할까? 첫번째로는 에라토스테네스의 체를 사용해 범위 내에서 소수를 빠르게 구할 수 있을 것이다. 에라토스테네스의 체는 소수의 배수를 제거하는 방식으로 O(Nlog(logN))의 시간복잡도를 가진다. 두번째로는 투포인터 알고리즘을 사용해 소수의 누적합을 빠르게 구할 수 있을 것이다. 따라서 N 범위 내의 소수 개수만큼만 순회하면 되기에 O(N)보다 적은 시간복잡도를 가지게 된다.

import sys

def make_prime(N):
    arr = [False,False]+[True for _ in range(2, N+1)]
    primes = []
    
    for i in range(2,N+1):
        if arr[i] == True:
            for j in range(2*i,N+1,i):
                arr[j] = False
    for i in range(len(arr)):
        if arr[i] == True:
            primes.append(i)
        
    return primes


def solution(N):
    if N ==1:
        return 0 
        
    answer = 0 
    total = 0 
    start,end = 0,0
    
    primes = make_prime(N)
    
    while True:
        if total >= N:
            total -= primes[start]
            start += 1
        elif end == len(primes):
            break
        else:
            total += primes[end]
            end += 1

        if total == N:
            answer += 1

    return answer
  
        


N = int(sys.stdin.readline())
print(solution(N))