[Python] 백준 / gold / 1644번 (소수의 연속합)

문제 링크 : https://www.acmicpc.net/problem/1644

투 포인터 + 소수 판별의 재밌는 문제다. 처음에 에라토스테네스의 체가 O(N x loglogN) time인 걸 알기 때문에 그걸로 풀었는데, 시간 초과가 나왔다,,
그래서 O(N^1/2)time의 소수 판별 함수를 사용했는데 그것도 시간 초과가 나왔다. 응 ..?
Pypy로 에라토스테네스를 제출하니 정답 처리되었다.

소수판별 함수 코드

import sys
import math
N = int(sys.stdin.readline())

if N == 1:
    print(0)
    exit(0)
elif N == 2:
    print(1)
    exit(0)


def check(x): # O(N^1/2)
    if x == 1: return False
    elif x == 2: return True
    for i in range(2, int(math.sqrt(x))+1):
        if x % i == 0:
            return False
    return True


prime = []

for i in range(2, N+1): # O(N)
    if check(i): prime.append(i)

end = 0
interval_sum = 0
answer = 0

for start in range(len(prime)):
    while end < len(prime) and interval_sum < N:
        interval_sum += prime[end]
        end += 1

    if interval_sum == N:
        answer += 1

    interval_sum -= prime[start]

print(answer)

에라토스테네스의 체 코드

import sys
import math
N = int(sys.stdin.readline())

arr = [True]*(N+1)
arr[0] = arr[1] = False

if N == 1:
    print(0)
    exit(0)
elif N == 2:
    print(1)
    exit(0)

for i in range(2, int(math.sqrt(N))+1):
    x = 2
    while i * x <= N:
        arr[i*x] = False
        x += 1

prime= []

for i in range(len(arr)):
    if arr[i]:
        prime.append(i)

end = 0
interval_sum = 0
answer = 0

for start in range(len(prime)):
    while end < len(prime) and interval_sum < N:
        interval_sum += prime[end]
        end += 1

    if interval_sum == N:
        answer += 1

    interval_sum -= prime[start]

print(answer)