[BOJ] 1644 / 소수의 연속합 / Python 파이썬

[BOJ] 1644 / 소수의 연속합 / Python 파이썬

[BOJ] 1644 / 소수의 연속합 / Python 파이썬

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

1644번: 소수의 연속합

 

 

풀이

연속된 소수의 합으로 입력된 숫자를 만드는 경우를 구하는 문제이다.

 

에라토스테네스의 체를 이용하여 소수 배열을 구해주고, 두 포인터로 구간을 잡아 구해주었다.

 

N = int(input())

primes = [1] * (N+1)
primes[0] = 0

nums = []

for i in range(2, N+1):
    if not primes[i]:
        continue
    nums.append(i)
    for j in range(i + i, N+1, i):
        primes[j] = 0

s, e = 0, 1
if nums:
    add = nums[s]

L = len(nums)

res = 0


while L:
    if e == L and add < N:
        break

    if add == N:
        res += 1
        add -= nums[s]
        s += 1
    elif add > N:
        add -= nums[s]
        s += 1
    else:
        add += nums[e]
        e += 1

print(res)