BaekJoon 1644번 : 소수의 연속합 (python)

BaekJoon 1644번 : 소수의 연속합 (G3 41.116%)

해당 문제는 위의 문제와 유사하지만 소수들이 배열을 이용해야 한다는 차이점이 있다.
결국 소수를 또 효율적으로 구해줘야 하는 문제이기에 에라토스테네스의 체를 이용한다.

제일 처음에는 set자료형을 이용해서 빠르게 구하는 방식을 사용했는데 이 방식을 사용했을 때 메모리 초과가 떠버리는 문제가 발생한다.
에라토스테네스의 체를 set자료형을 이용해 구했을 때의 비효율적인 이유와 에라토스테네스의 체를 조금 더 효율적으로 구할 수 있는 변수 설정을 밑에서 GPT가 알려준다.

• 넉넉하게 입력받는 N까지의 소수를 구하기 위해 bool리스트를 이용한 에라토스테네스의 체 알고리즘을 이용해서 N까지의 소수 리스트를 생성해준다.
• 위 문제와 동일하게 부분합, 구간합을 구해야하는 문제이기에 누적합을 이용한다.
• s와 e를 0과 1에서 시작하여 target값과 구간합이 같다면 count+=1을 해주고 구간합이 target값보다 작을 경우 e포인터를 증가시켜 구간합을 늘려준다.
• 만약 target값보다 구간합이 클 경우 구간합을 줄여주기 위해 s포인터를 증가시켜준다.

import sys
input = sys.stdin.readline

N = int(input())
arr = list()
num = [False]*(N+1)

for i in range(2, N+1) :
    if not num[i] :
        arr.append(i)
        for j in range(i*i,N+1,i) :
            num[j] = True

d = [0]
for i in arr :
    d.append(d[-1] + i)

s = 0 
e = 1
count = 0 
while e < len(d) :
    current = d[e] - d[s]
    if current == N :
        count += 1
        s+=1
    elif current > N :
        s+=1
    elif current < N :
        e+=1
print(count)