[BOJ] Q1644 소수의 연속합

[BOJ] Q1644

Question

Language: Python

Difficulty: Gold 3

주어진 숫자를 연속된 소수의 합으로 나타낼 수 있는 지 여부를 판단하는 문제이다.

이 문제의 핵심은

1. 소수 판별법
2. 연속된 숫자의 합의 개수

소수 판별법은 제곱근을 이용한 방식과, 에라토스테네스의 체를 이용하는 방식이 있는데, 해당 문제에는 소수의 집합이 필요하므로 에라토스테네스의 체를 활용한다.,

연속된 숫자의 합의 개수, 즉 부분합의 개수는 start, end 두 개의 포인터를 활용한 two-pointer을 활용하는 것이 좋다.

Solution

#에라토스테네스의 체
def era_filter():
    primes=[True] * (n+1)

    primes[0]=False
    primes[1]=False

    for i in range(2,n+1):
        if primes[i]==False:
            continue
            
        times=2
        while i*times < n+1:
            primes[i*times]=False
            times+=1
    
    return [i for i in range(2,n+1) if primes[i]]
    
def solution():
    primes=era_filter()
    if n==1:
        print(0)
        exit(0)
    
    count=0
    start=0
    end=0
    length=len(primes)
    sub_sum=primes[0]
#투 포인터
    while True:
        if sub_sum > n:
            sub_sum-=primes[start]
            start+=1
        else:
            if sub_sum==n:
                count+=1
            end+=1
            if end ==length:
                break
            sub_sum+=primes[end]
    print(count)        


if __name__ == "__main__":
    n=int(input())
    solution()