[백준] 1644 소수의 연속합 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/1644
• 🔑 에라토스테네스의 체를 사용해 소수 찾기
  • 먼저 시간초과가 나지 않으려면 소수를 찾을 때 에라토스테네스의 체를 사용해야 한다.
  • n까지의 소수를 미리 구해놓는다.
  • start, end 두 개의 포인터를 사용 (0, 0)
  • 첫 번째 소수부터 시작해서 소수의 합이 n보다 작으면 end 포인터를 한 칸씩 오른쪽으로 옮긴다.
  • 합이 n이 되면 정답을 올린다.
  • 합이 n보다 커지커나 같아지면 start 포인터를 한 칸씩 오른쪽으로 옮긴다.
  • 위 방법 반복
  • 끝 ✨

 

n = int(input())

prime_check = [True] * (n+1)    # 소수의 배수들을 체크

for i in range(2, int(n ** 0.5) + 1):
    if prime_check[i]:
        for j in range(i*2, n + 1, i):  # 소수 자신을 제외한 배수에 체크
            prime_check[j] = False

prime_number = [i for i in range(2, n+1) if prime_check[i]] # 소수 리스트

answer = 0
sum = 0
start, end = 0, 0

while start < len(prime_number):
    if sum < n:
        sum += prime_number[end]
        if end != len(prime_number) - 1:    # end 포인터가 끝을 벗어나지 않게
            end += 1
    elif sum >= n:
        sum -= prime_number[start]
        start += 1
    if sum == n:
        answer += 1

print(answer)