[백준] 1644번 소수의 연속합 - 파이썬

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

1644번: 소수의 연속합

문제

N 이하의 숫자들 중 소수인 수의 합으로 N이 나오는 경우의 수

입력

첫 번째 줄 => N

풀이

투 포인트 알고리즘과 에라토스테네스의 체 알고리즘을 합쳐서 풀어냈다.

1, 에라토스테네스의 체 알고리즘으로 N이하의 소수로 이루어진 리스트를 만든다.

2, 투포인트 알고리즘 사용으로 풀어낸다.

# 1644번 소수의 연속합
# 여러개의 소수, 투 포인터 알고리즘 사용 n의 범위 => (1 ≤ n ≤ 4,000,000)
n = int(input())
arr = [True for _ in range(n+1)]

# 에라토스테네스의 체 알고리즘
def primes_li(N):
    for i in range(2, int(N**0.5)+1):
        if arr[i]:
            for j in range(i*2, N+1, i):
                arr[j] = False
    return [i for i in range(2, N+1) if arr[i]]

# 투포인트 알고리즘
def solve(list):
    ans = 0
    end = 0
    interval_sum = 0
    for start in range(len(list)):
        while interval_sum < n and end < len(list):
            interval_sum += list[end]
            end += 1
        if interval_sum == n:
            ans += 1
        interval_sum -= list[start]
    print(ans)

primes = primes_li(n)
solve(primes)

출력결과