문제
[실버3] https://www.acmicpc.net/problem/1929
아이디어
1. 제곱근까지만 검사
소수를 구할 때 가장 중요한 부분은, 2부터 어디까지 반복하며 소수인지 판별하는가 이다.
n이 소수인지 판별할 때, 2부터 n-1까지 나누며 나머지가 0인 게 있는지 확인하는 것이 보편적으로 생각하는 방법이다. 이렇게 하면 한개의 숫자에 대해 소수여부를 판단하는 데 O(N)의 시간복잡도를 갖는다.
-> 그러나 n-1까지 반복하지 않고, 2부터 n의 제곱근까지만 반복해도 된다.
예를 들어 12가 소수인지 판별할 때(N=12)를 살펴보자.
12의 약수는 1, 2, 3, 4, 6, 12이고,
1과 12을 제외했을 때 이는 26, 34, 43, 62로 이들의 관계는 몫이 커지면 나누는 값이 작아지고, 나누는 값이 커지면 몫이 작아지는 반비례 관계이다.
결국, N의 제곱근(12의 제곱근 = 약 3.46) 까지 향하면 이후 몫과 나누는 값이 반대로 바뀌기만 한다는 것이다.
따라서 N이 소수인지 판별할 때 N-1까지가 아닌, N의 제곱근까지 나누어 떨어지는지 여부를 조사하면 더 빠르게 소수 판별을 할 수 있다.
이렇게 판별할 때의 시간복잡도는 O(sqrt(n))이다.
2. 에라토스테네스의 체
소수의 배수들을 지워나가고, 마지막으로 남아있는 수가 소수이다.
소수(x)의 배수는 약수로 무조건 x를 포함하게 된다.
따라서 소수의 배수는 절대 소수가 될 수 없다. 이를 이용한 것이 에라토스테네스의 체이다.
가장 작은 소수인 2부터 시작하여 2의 배수를 모두 지웠으면, 지워지지 않은 수 중에서 다음 값인 3을 제외하고, 3의 배수를 지워나가고 이를 반복해 나가면 소수만 남게 된다.
1번에서 보았듯, 반복문은 n의 제곱근(정수형으로 나타내야 하므로 int(n**0.5))까지 수행하면 된다.
예를 들어 n=12일 때 12의 약수는 1 2 3 4 6 12이다.
int(sqrt(12)) = 3이고, 3까지 반복하면 1부터 12 사이의 약수를 판별할 수 있다.
자세한 풀이
1부터 12 사이의 소수를 구하자.
1은 소수가 아니므로 2부터 시작한다.
int(sqrt(12)) = 3 이므로 4보다 작은 수의 배수(즉, 3까지만) 제거하면 된다.
- 2에서 시작 ) 자기 자신을 제외한 2의 배수 모두 제거
- 남아있는 숫자 중 가장 작은 수는 3이다. 3을 제외한 3의 배수 모두 제거
3까지만 반복하면 되므로, 이때 남은 수들이 모두 소수이다.
따라서 1부터 12 사이의 소수는 2, 3, 5, 7, 11이다. (1은 소수가 아니다.)
에라토스테넨스의 체를 이용하면 모든 수를 검사할 필요가 없기 때문에
검사해야 하는 범위가 클수록 효과적이고, 시간복잡도가 감소한다.
O(N) 에서 O(N^1/2)로 감소
풀이
import math
m, n = map(int, input().split())
prime = [True] * (n+1) # 모든 수가 소수(True)로 초기화
for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지
if prime[i]: # i가 소수라면
j = 2
while i * j <= n: # 범위 내의 i의 배수를 모두 False로
prime[i*j] = False
j += 1
if m <= 1:
m = 2
for i in range(m, n+1):
if prime[i]:
print(i)
Comment
기본적인 소수를 구하는 방식으로 이 문제에 접근하면 시간초과가 뜬다.
문제에서 M과 N의 범위가 1부터 100만까지로 매우 크기 때문에 N의 제곱근까지만 판별하고, 에라토스테네스의 체를 이용해야 함을 파악했다.
M과 N 사이의 수(x라 칭하면)에 대해 하나하나 2부터 x-1의 제곱근까지 나누며 소수인지 판별하는 과정을 N-M+1번 반복하는 것보다
에라토스테네스의 체를 이용하면 특정 범위 내에 소수를 한번에, 빠르게 찾을 수 있다.
