소수의 연속합 ( 1644 번 )

1644번: 소수의 연속합

 

🧠 알고리즘

_mk() : 에라토스테네스 체를 이용해 2부터 n까지 소수 구함
_main() : 투 포인터 방식으로 소수 리스트 내 연속된 소수 합이 n이 되는 경우 확인

 

🧾 코드

import sys

def _mk(num): # 에토체 (0: 소수 아님, 1: 소수)
    answer = [1] * (num + 1)
    answer[0], answer[1] = 0, 0
    for i in range(2, int(num ** (1/2)) + 1):
        if answer[i]:
            for j in range(i * i, num + 1, i):
                answer[j] = 0

    return [i for i in range(len(answer)) if answer[i]]


def _main(num, sosu_list): # 투 포인터
    answer = 0
    now_sum, max_len = 0, len(sosu_list)
    l, r = 0, -1

    while True:
        if now_sum <= num:
            if now_sum == num:
                answer += 1
            r += 1

            if r == max_len:
                break
            now_sum += sosu_list[r]

        elif now_sum > num:
            now_sum -= sosu_list[l]
            l += 1

    return answer
    

n = int(sys.stdin.readline().rstrip())
sosu_list = _mk(n)
print(_main(n, sosu_list))

 

⏱️ 시간 복잡도

_mk(num) : 에스테라토스 ( 선형 로그 시간 복잡도 )
_main(num, sosu_list) : 투 포인터 ( 선형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 선형 로그 시간 복잡도 ( O(n log n) )