백준 1644번: 소수의 연속합 (Python)

접근

바로 이전에 풀었던 부분합 문제와 푸는 방식이 같았던 문제이다. 입력받은 n 까지의 소수를 모두 구한 후, 부분합에 사용했던 투포인터 알고리즘을 이용하여 부분합이 n과 일치할 때를 카운트하여 문제를 해결할 수 있다.

소수 구하기 참고 문제: 2021.03.25 - [코딩/백준 (Python)] - 백준 9020번: 골드바흐의 추측 (Python)

백준 9020번: 골드바흐의 추측 (Python)

부분합 투포인터 알고리즘 문제: 2021.04.24 - [코딩/백준 (Python)] - 백준 1806번: 부분합 (Python)

백준 1806번: 부분합 (Python)

코드

import sys

n = int(sys.stdin.readline())


def prime(n):
    primes = [True] * n
    for i in range(2, int(n**0.5) + 1):
        if primes[i] is True:
            for j in range(2 * i, n, i):
                primes[j] = False
    return [i for i in range(2, n) if primes[i] is True]


if n >= 2:
    primes = prime(n + 1)
    left, right = 0, 0
    tmp = primes[left]
    cnt = 0
    while left <= right:
        if tmp < n:
            right += 1
            if right == len(primes):
                break
            tmp += primes[right]
        elif tmp > n:
            tmp -= primes[left]
            left += 1
        else:
            cnt += 1
            tmp -= primes[left]
            left += 1
else:  # n = 1 일 때, 1은 소수가 아니므로 0이다.
    cnt = 0
print(cnt)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!