[BOJ] 1644 소수의 연속합

https://www.acmicpc.net/status?user_id=rkdgur5381&problem_id=1644&from_mine=1

숫자 n을 n보다 작은 연속적인 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제이다.
먼저 n보다 작은 소수를 전부 구하고, 투포인터로 연속된 소수의 범위를 조절하면서 답을 구하려고 했지만 시간초과로 실패했다.

import math

n = int(input())

prime = [2, 3]

for i in range(4, n+1):
  chk = True
  for p in prime:
    if p > math.sqrt(i): break
    
    if i%p == 0:
      chk = False
      break
  if chk:
    prime.append(i)

start = 0
end = 1
tmp = prime[start]
answer = 0

while start < end and end <= len(prime):
  if tmp < n:
    if end < len(prime):
      tmp += prime[end]
    end += 1
  elif tmp >= n:
    if tmp == n:
      answer += 1
    tmp -= prime[start]
    start += 1
    
print(answer)

예전에 사용했던 소수 구하기 코드를 활용해서 시도했는데, 소수를 구하는 과정에서 400000정도에서 시간초과가 발생했다.
질문하기를 확인하니까 4,000,000 보다 작은 소수의 개수가 28만개가 있다고 하는데 내 코드는 최대 4,000,000 X 280,000이라서 시간초과가 난 것 같다.

지피티의 도움을 빌려서 에라토스테네스의 체를 활용했다.

n = int(input())

isPrime = [True] * (n+1)
isPrime[0] = isPrime[1] = False
p = 2

while p* p <= n:
  if isPrime[p]:
    for i in range(p*p, n+1, p):
      isPrime[i] = False
  p += 1

먼저 n+1칸의 배열을 True로 채우고, 0, 1은 False로 바꾼 다음 2부터 시작한다.
2부터 시작해서 p의 배수인 칸은 모두 False로 채우는 방식으로 소수와 소수가 아닌 숫자를 구분시켰다.
나머진 기존 코드를 활용하기 위해서 소수인 숫자만 다시 뽑아냈고, index 에러나 나서 마지막 연속합 구하는 코드를 조금 수정해서 문제를 해결했다.

에라토스테네스의 체를 활용하고 있다고 생각했으나 전혀 활용하지 않고 있었던 것을 알 수 있게된 문제였다.

n = int(input())

isPrime = [True] * (n+1)
isPrime[0] = isPrime[1] = False
p = 2

while p* p <= n:
  if isPrime[p]:
    for i in range(p*p, n+1, p):
      isPrime[i] = False
  p += 1
  

prime = []
for i, v in enumerate(isPrime):
  if v:
    prime.append(i)

start = 0
end = 0
tmp = 0
answer = 0

while start < len(prime):
  if tmp < n and end < len(prime):
    tmp += prime[end]
    end += 1
  else:
    if tmp == n:
      answer += 1
    tmp -= prime[start]
    start += 1
    
print(answer)