1644. 소수의 연속합

업데이트 시간 : 2023-08-16 01:45:35 +0000

[Gold III] 소수의 연속합 - 1644

문제 링크

성능 요약

메모리: 78764 KB, 시간: 1940 ms

분류

수학, 정수론, 소수 판정, 에라토스테네스의 체, 두 포인터

문제 설명

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

3 : 3 (한 가지)
41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

💡 Solutions

📄 소수의 연속합.py

import sys
import math

sys.setrecursionlimit(10 ** 8)
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
if n == 1:
    print(0)
    exit()

# 2 3 5 7 11 13 17 19 23 29 31 37 ...
# 4,000,000 == 2000^2
MAX = 4000000
is_prime = [1 for _ in range(n + 1)]
is_prime[0], is_prime[1] = 0, 0

for i in range(2, int(math.sqrt(n)) + 1):
    if is_prime[i]:
        for j in range(2, n // i + 1):
            is_prime[i * j] = 0  # 소수의 배수들은 다 소수가 아니므로 0으로 만듦

p = []
for i in range(2, n + 1):
    if is_prime[i]:
        p.append(i)

cnt = 0
i, j = len(p) - 1, len(p) - 1
cur = p[-1]
while 0 <= i <= j and 0 <= j < len(p):
    if cur > n:
        cur -= p[j]
        j -= 1

    else:
        if cur == n:
            cnt += 1
        i -= 1
        if i < 0:
            break
        cur += p[i]
print(cnt)