백준 1929번 풀이

문제

왜 안 나오나 했던 에라토스테네스의 체가 나왔다.

에라토스테네스의 체?

1~n까지의 범위에서 소수를 개 심플하고 빠르게 필터링하는 방법. 손으로 하나하나 지워가는 노가다가 필요하지만 아무튼 가장 빠르다… 에라토스테네스의 체를 이용하는 방법은 개 간단한데

1. 2를 제외한 2의 배수를 지운다
2. 3을 제외한 3의 배수(중 홀수)를 지운다
3. 5를 제외한 5의 배수(중 5로 끝나는 수)를 지운다
4. 7을 제외한 7의 배수(중 홀수)를 지운다

끝이다.

풀이

일단… 에라토스테네스의 체 자체는 간단한데, 이 문제는 시간초과가 걸려 있다. 그니까 내가 내라는 코드 안 내면 시간초과가 여러분을 반겨요…

import sys
M, N = map(int,sys.stdin.readline().split())
def isprime(a):
    if a < 2:
        return False
    for i in range(2,a):
        if a % i == 0:
            return False
    else: 
        return True
for i in range(M,N+1):
    if isprime(i):
        print(i)
    else:
        pass

에라토스테네스의 체는 이렇게만 해도 된다. 되긴 되는데 이거 그대로 내면 시간초과가 응애 나 애기시간초과! 하면서 반긴다.

출력은 비교적 호다닥 되니까 별로 체감이 안되겠지만, 저게 저대로 돌아가면 100이 소수인지를 알아보기 위해 100을 2부터 100까지로 쫙 다 나눠야 한다. 100은 2로 나눠떨어지니까 금방이죠… 91은 소수여… 그럼 어느세월에 나누겠음.

import sys
M, N = map(int,sys.stdin.readline().split())
def isprime(a):
    sqrt = int(a ** 0.5)
    if a == 1: 
        return False
    for i in range(2,sqrt+1):
        if a % i == 0:
            return False
    else: 
        return True

for i in range(M,N+1):
    if isprime(i):
        print(i)

그래서 이걸로 내야 한다.

뭐야 제곱근이 왜 저기서 나와요? 그… 자, 일단 에라토스테네스의 체 알고리즘이 어떤 수(보통 소수)로 나눠서 나머지가 0이면 소수가 아님! 이라고 했는데, 그 수가 사실은 쫘라락 나눌 필요가 없고 소수 찾을 범위에 있는 수 n의 제곱근까지만 나누면 된다. 그러니까, 1부터 100까지면 루트 100 해서 10의 배수까지만 지우면 된다. (120도 10의 배수까지만) 150은 가장 가까운 제곱수가 121이라 11의 배수까지 구해야 한다.