백준|1644번|소수의 연속합

문제 순서

숫자 N을 소수의 연속 합으로 나타내는 방법의 가짓수를 출력하는 문제입니다.
소수의 연속합: 이어지는 소수들의 합으로 2+3+5는 연속합이지만 2+5는 연속합이 아님

작동 순서

1. 숫자 N을 입력받습니다. 만약 N이 2 미만일 경우 2 이하의 소수는 없으므로 0을 출력하고 종료합니다.
2. 에라토스테네스의 체를 활용하여 숫자 N 이하의 소수를 모두 구합니다.
3. 배열을 만든 뒤 N 이하의 소수들을 순서대로 저장합니다.
4. 연속합 num에 첫 번째 소수를 더해주고 인덱스 위치를 first:0-end:0(0번부터 0번까지의 합)으로 지정해줍니다.
5. num이 N과 같은 경우 count를 +1 해주고 first와 end를 모두 1씩 올려줍니다. 이 과정에서 num에서 현재의 first번째 소수를 빼주고 새로운 end번째 소수를 더해줍니다.
6. num이 N보다 작은 경우 숫자를 크게 만들어야 하므로 end를 +1해주고 num에 새로운 end번째 소수를 더해줍니다.
7. num이 N보다 큰 경우 숫자를 작게 만들어야 하므로 num에서 first번째 소수를 빼주고 first를 +1해줍니다.
8. 소수 범위를 다 체크하고 나면 count를 출력하고 프로그램을 종료합니다.

소스코드

import math

N = int(input())

if N < 2:
    print(0)
else:
    is_primeNumber = [True]*(N+1)
    is_primeNumber[0], is_primeNumber[1] = False, False
    primeNum = []

    for i in range(2, math.ceil(math.sqrt(N+1))):
        if is_primeNumber[i]:
            n = i+i
            while n < N+1:
                is_primeNumber[n] = False
                n += i

    for i in range(2, N+1):
        if is_primeNumber[i]:
            primeNum.append(i)

    first = 0
    end = 0
    num = primeNum[0]
    length = len(primeNum)
    count = 0
    while first < length and end < length:
        if num == N:
            count += 1
            num -= primeNum[first]
            first += 1
            end += 1
            if end == length:
                break
            num += primeNum[end]
        elif num < N:
            end += 1
            if end == length:
                break
            num += primeNum[end]
        else:
            num -= primeNum[first]
            first += 1
    print(count)