[백준] 소수의 연속

https://www.acmicpc.net/problem/1644

문제 정리

• 자연수를 연속된 소수의 합으로 나타내기 (중복x)
• 시간 2초, 자연수 최대 : 4,000,000

풀이 과정

시간이 빠듯하기에 O(N)이하의 시간 복잡도로 가져간다고 생각
먼저 필요한 수는 소수만 필요하기에 소수를 먼저 뽑아준다.
2 ~ N까지의 수를 뽑아야 하며, 이때 어떤식으로 뽑을지 고민
만약 2 ~ N까지 각 수마다 하나씩 if n % i == 0 과 같은 방식으로 소수를 판별하면 시간이 오래걸린다.
이에 에라토스테네스의 체 방식(def is_prime)으로 소수를 구함으로써 계산 시간을 최대한 줄인다.

그 다음 연속된 소수의 합(total)이 N이 되는지 파악하기 위해 포인터 2개(st, en)를 사용하여 total이 N보다 크다며 en을 증가시키고, 아니라면 st를 증가시킨다.

물론 total이 N과 같다면 경우의 수를 1 증가시키고
en을 증가시키냐, st를 증가시키냐에 따라 total도 늘리거나 줄어야한다.

n = int(input())

def is_prime(x):
    
    prime = [True] * (n + 1)
    prime[0] = prime[1] = False

    for i in range(2, int(n**0.5) + 1):
        
        if prime[i]:
            for j in range(i*i, n + 1, i): # i의 배수 제거 -> n까지
                prime[j] = False

    return [i for i in range(2, n+1) if prime[i]]



st = en = cnt = 0
board = is_prime(n)
board.append(0)
total = board[st]

for st in range(len(board)): # st 끝까지

    while en < len(board) - 1 and total < n:
        en += 1
        total += board[en]
    
    if en == len(board): break

    if total >= n:
        if total == n: cnt += 1
        total -= board[st]

print(cnt)