가장 먼저 소수를 구하는 문제가 공용으로 쓰는 알고리즘이 있다.
소수를 판별하는 알고리즘으로 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 소수와 관련된 문제가 출제되면 항상 에라토스테네스의 체를 사용할 준비가 되어있어야 한다.
에라토스테네스의 체는 가장 먼저 소수를 판별할 범위(Bool형식)만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 배수들을 지워나가는 방법을 이용한다.
def eratosthenes_sieve(N):
IsPrime[0] = IsPrime[1] = False
for i in range(2, int(N**0.5) + 1):
for j in range(i * 2, N + 1, i):
IsPrime[j] = False
prime = []
for i in range(N + 1):
if IsPrime[i]:
prime.append(i)
return prime
이 때 에라토스테네스의 체의 배수의 기준이 되는 i는 +1만큼만 반복한다.
- O()의 시간 복잡도로 매우 빠르게 소수들을 모두 찾을 수 있다.
소수 배열을 에라토스테네의 체로 얻었다고 가정할 때 연속된 소수의 합을 어떤 방식으로 구해야 할까? 투 포인터 방식을 이용해 구현했다. 연속되는 소수이기 때문에 시작점과 끝점의 위치를 안다면 해당 범위의 합을 구할 수 있다.
- 범위의 합 = N ? ans를 1 늘리고 시작접, 끝점을 +1 해준다.
- 범위의 합 > N ? 시작점을 +1 해준다.
- 범위의 합 < N ? 끝점을 +1 해준다.
이러한 시작점, 끝점처럼 두 개의 포인터를 이용한 연산은 "연속된"과 "졍렬된"이 둘다 만족할 때 사용 가능하다.
소수가 정렬된 상태로 prime 배열에 들어가있고 연속된 소수의 합을 구하는 문제이므로 투 포인터를 이용해 빠르게 실행 가능하다.
코드로는 다음과 같이 구현할 수 있다.
ans = 0
start = 0
end = 1
while start < end and end <= len(prime):
s = sum(prime[start:end])
if s == N:
# print(start, end)
ans += 1
start += 1
end += 1
elif s < N:
end += 1
elif s > N:
start += 1
이러한 투 포인터 방식의 장점은 굉장히 적은 시간으로 O(N)의 시간 복잡도로 계산을 할 수 있다.
- 결국 s, e가 배열 전체를 한 번 훑으면 끝나기 때문이다.
기존에는 반복문을 이용해서 하나만 더하는 경우, 두 개만 더하는 경우, 모든 경우를 따져서 더했을때 N보다 커지면 continue 하는 과정으로 구현을 했으나. N가 최대 4,000,000 들어오면 1을 N번, 2를 N-1번, 반복하고 나면 시간 복잡도가 O()이나 되기 때문에 실행 시간 초과 오류가 발생했다.
import sys
input = sys.stdin.readline
def eratosthenes_sieve(N):
IsPrime[0] = IsPrime[1] = False
for i in range(2, int(N**0.5) + 1):
for j in range(i * 2, N + 1, i):
IsPrime[j] = False
prime = []
for i in range(N + 1):
if IsPrime[i]:
prime.append(i)
return prime
N = int(input())
IsPrime = [True] * (N + 2)
prime = eratosthenes_sieve(N)
# print(prime)
ans = 0
start = 0
end = 1
while start < end and end <= len(prime):
s = sum(prime[start:end])
if s == N:
# print(start, end)
ans += 1
start += 1
end += 1
elif s < N:
end += 1
elif s > N:
start += 1
print(ans)