BOJ/백준-1644-python

문제📖

풀이🙏

• 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)
• 첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

코드💻

# boj, 1644 : 소수의 연속합, python3
# 에라토스테네스의 체, 투 포인터
N = int(input())


def eratos(n):
    sieve = [1] * (n + 1)

    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i]:
            for j in range(i * 2, n + 1, i):
                sieve[j] = 0

    return [i for i in range(2, n + 1) if sieve[i]]


def solution():
    primes = eratos(N)

    if not primes:
        return 0

    answer = 0
    head, tail = 0, 0
    acc = primes[0]

    while head <= tail:
        if acc < N:
            tail += 1
            if tail < len(primes):
                acc += primes[tail]
            else:
                break
        else:
            if acc == N:
                answer += 1
            acc -= primes[head]
            head += 1

    return answer


print(solution())

결과😎

출처 && 깃허브📝

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