[Python/파이썬] 백준 1644번 - 소수의 연속합

문제 설명

 

입출력 예제

 

---

풀이 코드

연속된 소수의 합을 구하기 위해서는 에라토스테네스의 체를 이용해 N까지의 소수를 구하고,

구한 소수 배열을 바탕으로 투 포인터를 활용해 연속된 소수의 합이 N이 되는지를 확인하여 정답을 구할 수 있다.

 

에라토스테네스의 체와 투 포인터에 대한 설명은 아래 링크에서 참고할 수 있다.

[알고리즘] 투 포인터(Two Pointers)란?

[Java/자바] 프로그래머스 - 소수 찾기 (에라토스테네스의 체)

 

 

정답 코드

import sys
input = sys.stdin.readline

N = int(input())

# 소수 배열
primes = [True] * (N + 1)

# 0과 1은 소수가 아니므로 False
primes[0] = False
primes[1] = False

# 소수 구하기 (에라토스테네스의 체 알고리즘)
for i in range(2, int(N ** 0.5) + 1):
    if primes[i]:
        for j in range(i + i, N + 1, i):
            primes[j] = False

# 소수 여부 boolean을 숫자로 초기화
primes = [i for i in range(2, N+1) if primes[i]]

# 투 포인터
start = 0
end = 0
total = 0
cnt = 0

while True:
    if total == N:
        cnt += 1
        
    if total > N:
        total -= primes[start]
        start += 1
    elif end == len(primes):
        break
    else:
        total += primes[end]
        end += 1

print(cnt)