1644 - 소수의 연속합

LeeKyoungChang·2022년 4월 10일
0

Algorithm

목록 보기
100/203
post-thumbnail

📚 1644 - 소수의 연속합

소수의 연속합

 

이해

투 포인터 문제를 많이 풀어본 사람들은 금방 해결할 문제이다!

✏️ 투 포인터 특징
arr 배열이 있을 때
start : 배열에서 검토 시작점
end : 배열에서 검토 끝점

startend 사이를 검토해가며, 연속된 소수의 합이 몇 가지인지 구하면 된다!

추가로, 소수 구하는 반복문을 통해 소수들을 구하면 된다.

 

소스

import sys

# INF = 4000010

read = sys.stdin.readline

n = int(read())

if n == 1:
    print(0)
    sys.exit()

decimal = []
decimalCheck = [False] * (n+1)


def decimalFun():
    for i in range(2, n+1):
        if not decimalCheck[i]:
            decimal.append(i)
            for j in range(i + i, n+1, i):
                decimalCheck[j] = True

# 소수
decimalFun()

start = 0
end = 0
permission = decimal[0]

cnt = 0

while True:
    if permission == n:
        cnt += 1

    if permission >= n:
        permission -= decimal[start]
        start += 1
    else:
        end += 1

        if end == len(decimal) or decimal[end] > n:
            break
        permission += decimal[end]

print(cnt)
스크린샷 2022-04-10 오후 11 41 05

 

profile
"야, (오류 만났어?) 너두 (해결) 할 수 있어"

0개의 댓글