백준: 1644 소수의 연속합

문제

1644번: 소수의 연속합

 

문제 풀이

 이 문제는 수들의 합 2, 부분합 문제에서 소수의 합으로 나타낼 수 있는 경우의 수를 찾는 문제이다. 연속합을 구하는 로직은 앞서 다룬 2 문제와 동일하며, 소수를 구하는 부분만 추가하면 쉽게 풀 수 있는 문제이다.

 

코드

from sys import stdin


def is_prime(num):
    find = []
    check = [True] * (num + 1)
    check[1] = False

    for i in range(2, num + 1):
        if check[i]:
            find.append(i)
        for j in range(i * i, num + 1, i):
            check[j] = False

    return find

if __name__ == '__main__':
    answer = start = end = 0
    n = int(stdin.readline())
    primes = is_prime(n)

    subtotal = [0] * (n + 1)
    for i in range(1, len(primes) + 1):
        subtotal[i] = subtotal[i - 1] + primes[i - 1]

    while True:
        cur_subtotal = subtotal[end] - subtotal[start]

        if cur_subtotal == n:
            answer += 1
            start += 1
        elif cur_subtotal > n:
            start += 1
        elif end == len(primes):
            break
        else:
            end += 1

    print(answer)