[백준] 1644 : 소수의 연속합

비가츄·2024년 2월 23일

python 백준

문제 설명

소수의 연속합 문제의 링크는 아래와 같다.
소수의 연속합

하나 이상의 연속된 소수로 만들어낼 수 있는 자연수가 있다.
이에 대한 예는 다음과 같다.

3 : 3 (한 가지)
41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
53 : 5+7+11+13+17 = 53 (두 가지)

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하면 된다.

자연수 N : 1 < N < 4,000,000
시간 제한 : 2초

접근

단순 구현

일단 떠오르는 대로 구현해보았다.

에라토스테네스의 체로 소수의 집합을 구한다.
구하는 과정에서 누적합을 통해 연속된 소수의 합을 구한다.
2-1. 연속된 소수의 합이 N이면 answer에 1을 더한다.
2-2. 연속된 소수의 합이 N보다 큰 경우 이전 누적합을 순서대로 빼며 N이 되는 경우를 찾는다.
answer를 출력한다.

코드는 다음과 같다

# 소수의 연속합 :GOLD 3
N = int(input())
answer = 0
A = [True for _ in range(N+1)]
PS = [0] # 소수 누적합을 저장할 배열

# 에라토스테네스의 체를 통해 소수 구하기
for i in range(2, N+1):
    if not A[i]:
        continue
        
    for k in range(i*2, N+1, i):
      	A[k] = False
    
    # 연속된 소수의 합을 구해 저장(누적합)
    PS.append(PS[-1]+i)

    # 연속된 소수의 합이 N이면 answer + 1
    if PS[-1] == N:
        answer += 1
    
    # 연속된 소수의 합이 N보다 크면 반복문으로 N 되는 경우 연산
    if PS[-1] > N:
        for p in PS:
            temp = PS[-1] - p

            if temp > N:
                continue
            
            if temp == N:
                answer += 1
            break

print(answer)

해당 코드는 정답이 나오지만, N의 최대값인 4,000,000을 입력하면 2초 이상의 연산 시간이 소요된다.
위의 코드에서 2번과정만 시간복잡도가 대략 O(N^2)인데, 4,000,000보다 작은 소수는 283,147개이기 때문이다.

Queue를 이용한 구현

생각해보니 굳이 누적합을 이용할 필요가 없다는 생각이 들었다.
애초에 단순하게 하나의 변수를 두고 이곳에 모든 소수를 더하고, N보다 큰 경우 가장 먼저 넣었던 소수를 빼면 되는 것 아닐까?

에라토스테네스의 체로 소수의 집합을 구한다.
찾은 소수들을 temp에 모두 더한다.
2-1. temp가 N보다 큰 경우 가장 먼저 더했던 소수를 뺀다.
2-2. temp가 N인 경우 answer에 1을 더한다.
answer를 출력한다.

코드는 다음과 같다.

...
N = int(input())
answer = 0
A = [True for _ in range(N+1)]
temp = 0
queue = deque()

# 에라토스테네스의 체를 통해 소수 구하기
for i in range(2, N+1):
    if not A[i]:
        continue

    for k in range(i*2, N+1, i):
        A[k] = False
    
    # 소수만 따로 저장
    queue.append(i)

    temp += i
    while temp > N and queue:
        temp -= queue.popleft()
        
    if temp == N:
        answer += 1

print(answer)

소스코드

최종적으로 제출한 코드는 다음과 같다.

from collections import deque

# 소수의 연속합 :GOLD 3
N = int(input())
answer = 0
A = [True for _ in range(N+1)]
temp = 0
queue = deque()

# 에라토스테네스의 체를 통해 소수 구하기
for i in range(2, N+1):
    if not A[i]:
        continue

    for k in range(i*2, N+1, i):
        A[k] = False
    
    # 소수만 따로 저장
    queue.append(i)

    temp += i
    while temp > N and queue:
        temp -= queue.popleft()
        
    if temp == N:
        answer += 1

print(answer)