BOJ 1929 : 소수 구하기

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

풀이

소수 구하는 문제라고 되어 있는데, 기존 방식대로 그리디하게 풀게 되면 시간 초과가 발생한다.(1 ~ 1000000)영역을 줄 경우. 그래서 이틀 테스트 해보고 실패해보고, 찾은 소수의 배수만큼을 미리 빼 버리면 될까? 싶어서 찾아보니 역시... 이미 예전에 누군가가 생각을 했던 문제였다. '에라토스테네스의 체'라는 방법인데, 체는 '거름 망'이다. 이것은 이미 구해둔 값의 이후 뒷 부분은 다시 반복 될 필요가 없기 때문에 앞으로 계산 할 부분에서 빼버리는 기법인데, 아이디어가 충분히 소수 구하는 문제 외에도 고안될 수 있을 것 같다.

※ 다만, 안전과 관련된 부분에서는 쉽게 적용 했다가 문제가 생길 것 같기도 함.

 

여튼, 벤치마킹(99%)의 코드는 다음과 같다.

import sys

def eratosthenes(n, m):
    check = [0] * (m + 1)
    result = []
    for i in range(2, m + 1):
        if check[i] == 0:
            for j in range(i*2, m + 1, i):
                if check[j] == 0:
                    check[j] = 1

    for i in range(n, m+1):
        if check[i] == 0:
            result.append(i)
    if 1 in result:
        result.remove(1)
    return result

if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())

    for e in eratostenes(n, m):
        print(e)

1. 내가 찾아야 하는 범위 까지 수(m)와 시작 범위의 수(n)를 입력 받는다.
2. 입력 받은 수 까지 만큼 소수를 체크할 건데, 확인할 수의 체크 넘버가 '0'이면 확인이 안되었다는 것임.
3. 이것의 배수만큼(i) 증가하면서 '0'이면, 그 수는 앞 수의 배수가 되므로 소수인지 아닌지 후에 확인해 볼 필요가 없다는 것임.
4. 이로써 전체 배열을 확인 했을 때, 아직 배수로 지정되지 않은 수만 값을 정렬하여, 그 중 1만 빼고 출력한다.

아이디어도 거의 근접했긴 한데, 많이 어려운 문제였다.