[BOJ/백준] 1644 소수의 연속합

def get_prim_number(N):
    prime_check = [True]*(N+1)
    prime_check[0] = False
    prime_check[1] = True
    result = []

    for num in range(2,N+1):
        if prime_check[num]:
            result.append(num)
            for new_num in range(num*2,N+1,num):
                prime_check[new_num] = False
    
    return result


N = int(input())

prime_list = get_prim_number(N)
prefix_sum = prime_list[:]
for i in range(len(prime_list)-1):
    prefix_sum[i+1] += prefix_sum[i]

prefix_sum = [0] + prefix_sum


cnt = 0
left = 0
right = 0
while right <len(prefix_sum):
    temp = prefix_sum[right] - prefix_sum[left]

    if temp == N:
        cnt += 1
        right += 1
    elif temp < N:
        right += 1
    else:
        left += 1
        if temp == 0:
            left = right

print(cnt)

먼저 주어진 N까지의 소수들을 전부 구해준다.

 

그리고 구한 소수들을 prefix_sum으로 구간합을 구해준다.

 

두 포인터를 해주면 된다.

 

import math
import sys

input = sys.stdin.readline

def get_prim_number(N):
    prime_check = [True]*(N+1)
    prime_check[0] = False
    prime_check[1] = False
    result = []

    for num in range(2,int(math.sqrt(N))+1):
        if prime_check[num]:
            for new_num in range(num*2,N+1,num):
                prime_check[new_num] = False
    for num in range(2,N+1):
        if prime_check[num]:
            result.append(num)
    return result


N = int(input().strip())

prime_list = get_prim_number(N)
interval_sum = 0
left = 0
cnt = 0
for right in range(len(prime_list)):
    interval_sum += prime_list[right]

    while interval_sum > N:
        interval_sum -= prime_list[left]
        left += 1

    if interval_sum == N:
        cnt += 1

print(cnt)

 

위와 다른점은 소수를 구할때, 루트(N)까지만 반복을 해주는것과,

 

누적합을 미리 안 구하고, 앞에서부터 하나씩 더해가면서 right를 옮겨주고, N을 넘어가면 left를 늘려가면서 N인 경우를 찾아 주는 것이었다.