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

# 백준 1644 소수의 연속합
import math
def is_prime(num):
    sqrt_num=int(math.sqrt(num))+1
    for i in range(2,sqrt_num):
        if num%i==0:
            return False
    return True

primes=[]
N=int(input())
for num in range(2,N+1):
    if is_prime(num):
        primes.append(num)

ans=0
left=0
right=0
if N==1:
    print(0)
else:
    n=primes[0]
    len_primes=len(primes)
    while right<len_primes:
        if n>=N:
            if n==N:
                ans+=1
            if left<right:
                n-=primes[left]
                left+=1
            elif left==right:
                right+=1
                if right<len_primes:
                    n+=primes[right]
        else:
            right+=1
            if right<len_primes:
                n+=primes[right]

    print(ans)

맨 처음에는 에라스토테네스의 체를 이용한 방법이 아닌 1부터 N까지 소수 판별을 시도하였다. 

시간복잡도가 O(N log(N))으로 시간초과 발생하였다... (pypy3로는 통과)

 

import sys

# 입력값 N (1 ≤ N ≤ 4,000,000)
N = int(sys.stdin.readline())

# 소수 판별을 위한 리스트 초기화
primes = []
is_prime = [True] * (N + 1)
is_prime[0] = is_prime[1] = False  # 0과 1은 소수가 아님

# 에라토스테네스의 체로 소수 판별
for i in range(2, int((N**0.5) + 1)):
    if is_prime[i]:
        for j in range(i * i, N + 1, i):
            is_prime[j] = False

# 실제 소수 리스트 구성 (모든 소수를 포함)
primes = [i for i, val in enumerate(is_prime) if val]

# 투 포인터 초기화
ans = 0         # 조건을 만족하는 경우의 수
left = 0        # 왼쪽 포인터
right = 0       # 오른쪽 포인터
n = 2           # 현재 연속된 소수의 합 (초기값은 primes[0]과 같음)
len_primes = len(primes)

# 투 포인터 알고리즘 시작
while right < len_primes:
    if n >= N:
        if n == N:
            ans += 1  # 조건을 만족하면 정답 카운트
        if left < right:
            # 왼쪽 값을 빼면서 창을 줄임
            n -= primes[left]
            left += 1
        elif left == right:
            # left == right일 경우, 창 크기를 늘려줘야 하므로 right 증가
            right += 1
            if right < len_primes:
                n += primes[right]
    else:
        # n < N: 오른쪽 포인터를 이동시켜 합을 증가
        right += 1
        if right < len_primes:
            n += primes[right]

# 결과 출력
print(ans)

에라스토테네스의 체를 구현하여 해결하였다.

시간복잡도는 O(N log log (N)) 이라 훨씬 빠르다.

 

그 뒤로는 투포인터 써서 해결하며 된다.