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

이번에 해결해 볼 문제는 백준에 있는 1644번 소수의 연속합입니다.

---

문제 설명

• 이전에 해결해 봤던 2003번 수들의 합 2와 비슷합니다. 다른 점이라 한다면 연속된 수가 자연수가 아닌 소수라는 점입니다.

문제 해결 아이디어

• 해당 문제는 두 파트로 나눠 해결할 수 있습니다.
• 첫 번째, 소수를 찾는 파트입니다. 시간을 최대한 아끼기 위해 에라토스테네스의 체를 통해 소수를 찾아보고자 합니다.
• 두 번재, Two-Point를 사용해 연속 합을 구하는 부분입니다.

Tip

• 시간을 조금이나마 단축을 하기 위해 소수 찾는 부분에서 탐색 범위를 $2 \sim N$에서 $2 \sim \sqrt{N}+1$로 줄일 수 있습니다. 그러나 이 부분에서 실수가 나올 수 있고 저 또한 처음에 해당 부분에서 실수를 했습니다. 소수인지 아닌지 판단을 하며 소수를 따로 리스트에 저장해야 하는데 이 때 탐색 범위를 줄여버려서 소수가 덜 저장되는 문제가 발생합니다. 이를 방지하기 위해서는 탐색범위를 줄이지 않고 소수를 찾거나(소수 찾기 2) 소수인지 아닌지 판단하는 코드와 소수를 저장하는 코드를 분리(소수 찾기 1)해야 합니다. 아래에 두 코드를 모두 첨부했으니 소수를 찾는 부분에서 그 차이점을 확인하실 수 있습니다.
  
  💭 python time 모듈을 통해 저의 환경에서 테스트해 본 결과 소수 찾기 1이 조금 더 빨랐습니다.

  # 소수 찾기 1
  bool_prime = [False, False] + [True] * (N - 1)
  
  for i in range(2, int(N**0.5) + 1):
      if bool_prime[i]:
          for j in range(i + i, N + 1, i):
              bool_prime[j] = False
  
  prime = [i for i in range(2, N + 1) if bool_prime[i]]
  
  # 소수 찾기 2
  bool_prime = [False, False] + [True] * (N - 1)
  prime = []
  for i in range(2, N + 1):
      if bool_prime[i]:
          prime.append(i)
          for j in range(i * 2, N+1, i):
              bool_prime[j] = False
  

• 시간을 조금이라도 더 줄이고 싶다면 Two-Point 부분에서 더 줄일 수 있습니다. 현재 저의 코드는 리스트에 일정 부분의 합을 계속해서 더하고 있습니다.(val = sum(prime[start:end])) 찾는 숫자의 크기가 작다면 상관없지만 찾는 숫자의 크기가 크다면 해당 숫자를 찾기위해 점점 더 많은 숫자를 더해야 하는 문제가 발생하기 때문에 시간이 점점 더 증가할 수 밖에 없습니다. 따라서 이 부분을 개선한다면 시간을 단축할 수 있습니다. 해결 방법은 의외로 단순합니다. 두 개의 포인트를 하나씩 이동하므로 start가 움직이는 경우에는 기존의 합(val)에서 prime[start]를 빼주고 end가 움직이는 경우에는 기존의 합(val)에서 prime[end]를 더해주면 됩니다. 다만 여기에서 조심해야 할 점은 start를 이동시키고 prime[start]를 빼면 안되고 end를 움직이지 않고 prime[end]를 더해주시면 안됩니다.
  
  글로써 이해가 안가신다면 두 가지를 비교한 포스트의 코드를 통해 비교를 해볼 수 있습니다.

문제 해결 코드

import sys

input = sys.stdin.readline

N = int(input())

# 소수 찾기 1
bool_prime = [False, False] + [True] * (N - 1)

for i in range(2, int(N**0.5) + 1):
    if bool_prime[i]:
        for j in range(i + i, N + 1, i):
            bool_prime[j] = False

prime = [i for i in range(2, N + 1) if bool_prime[i]]

# Two-Point
answer = 0
start, end = 0, 1

while start < len(prime) and end <= len(prime):
    val = sum(prime[start:end])

    if val == N:
        answer += 1
        start += 1
        end += 1
    elif val > N:
        start += 1
    else:
        end += 1

print(answer)