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

Baekjoon online judge 1644번 파이썬

링크

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

부분합 + 에라토스테네스의 채

https://storkbear.tistory.com/25

백준 1806번 부분합 (Python 3)

위 문제와 같은 구조이다.

소스코드

import sys
input=sys.stdin.readline

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

n=int(input())
prime=prime_list(n+1)
left=0
right=0
ans=0

now=prime[0]

while left<len(prime):
    if prime[left]>n and prime[right]>n:
        break

    if now==n:
        ans+=1
        now -= prime[left]
        left += 1
    elif now>n:
        now-=prime[left]
        left+=1

    elif now<n:
        right+=1
        if right>=len(prime):
            break
        now+=prime[right]
print(ans)