[Python] 백준, 1644(두 포인터)

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

1644번: 소수의 연속합

 

소수를 구하는 알고리즘은 '에라토스테네스의 체'라는 이름으로 널리 알려져 있다. 밑의 코드에서도 구현하겠지만, 간단한 원리는 소개하는 게 좋을 것 같다.

 

1. 소수면 True, 아니면 False로 구성된 리스트를 만든다.

2. n ** 0.5 까지 반복문을 돌면서 소수면 그 배수들을 전부 False로 바꾼다.

3. 리스트에서 n까지 반복하며 값이 True인 인덱스를 구한다.

 

복잡한 듯 싶지만 꽤 간단하며 원리도 직관적이다.

 

이 문항은 에라토스테네스의 체와 두 포인터가 합쳐진 문젠데, 각각의 개념 자체는 어렵지 않지만 이런 식으로 응용시켜 놓는다면 조금 당황할 것 같기는 하다. 두 포인터는 이제 어느 정도 익숙하니 에라토스테네스의 체도 한 번 정도는 더 복습하는 게 좋을 것 같다.

 

 

# PYTHON CODE

n = int(input())

prime_bool = [False, False] + [True] * (n - 1)
m = int(n ** 0.5)

for i in range(2, m + 1):
    if prime_bool[i]:
        for j in range(i * 2, n + 1, i):
            prime_bool[j] = False

answer = [i for i in range(1, n + 1) if prime_bool[i]]

pl, pr = 0, 0
flag = 0
x = answer[0] if answer else 0

while x:
    if x > n:
        x -= answer[pl]
        pl += 1
    else:
        if x == n:
            flag += 1
        if pr == len(answer) - 1:
            break
        pr += 1
        x += answer[pr]

print(flag)