[Python] 1929 소수 구하기

📌 문제

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

📌 입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

📌 출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

📌 문제 풀이

👨‍🏫 접근

소수를 2중 for문으로 구하면 O(N2)이 걸리기 때문에 문제의 최댓값인 106을 제곱했을 때 1012이기 때문에 1000초가량 걸린다.

그런데 소수를 구하는 데에 있어서 그 수를 2부터 자기 자신까지 나누는 것이 아니라 자신의 제곱근만큼만 약수를 구하면 된다.

왜냐하면 제곱근 이후로 나누는 수와 몫이 서로 바뀌어 등장하기 때문이다. 예를 들어 16의 약수는 1, 2, 4, 8, 16으로 16의 제곱근 중 하나인 4를 지나가면 2의 몫인 8이 등장하므로 굳이 볼 필요가 없다.

그래서 소수를 한 번 구할 때 for문으로 전체 수를 돌아다니며 O(N), 그리고 그 수의 약수를 탐색하면서 O(√N)을 소요하기에 총 시간 복잡도의 소요는 O(N√N)가 된다.

---

물론 이렇게 끝낼 수도 있지만, 매번 O(√N)으로 탐색하는 것보다 탐색하면서 발견한 소수를 지워놓는 테이블이 있으면 굳이 다시 계산할 필요가 없을 것이다.

그래서 에라토스테네스의 체 알고리즘을 통해 더욱 빠르게 문제를 해결할 수 있다.

에라토스테네스의 체는 소수를 발견했을 때, 그 소수의 배수를 모두 제외하면서 최종적으로 소수만을 남기는 방식의 알고리즘이다. 예를 들어 2의 배수인 2, 4, 6, 8, 10, ...을 모두 제거하고, 3의 배수인 3, 6, 9, 12, 15, ...을 모두 제거하는 방법을 n까지 반복하여 소수만 있는 테이블을 생성하는 것이다. 이전에 계산했던 테이블을 계속해서 재사용하면서 시간 소요를 조금 더 줄일 수 있다.

이때, 에라토스테네스의 체의 시간 복잡도는 O(NloglogN)으로 선형 시간과 거의 근접하는 효율적인 알고리즘이다. 하지만, 리스트를 통해 수많은 정보를 저장하기 때문에 메모리 소요가 크다는 단점도 있다.

👨‍🏫 문제 풀이

📄 전체 코드

def prime_list(a, b):
    sieve = [True] * (b + 1)
    sieve[0], sieve[1] = False, False

    m = int(n ** .5)
    for i in range(2, m + 1):
        if sieve[i] == True:
            for j in range(i * 2, b + 1, i):
                sieve[j] = False

    return [i for i in range(a, b + 1) if sieve[i] == True]

m, n = map(int, input().split())

print(*prime_list(m, n))

📄 준비

def prime_list(a, b):
    sieve = [True] * (b + 1)
    sieve[0], sieve[1] = False, False

매개변수 a는 시작 인덱스, b는 종료 인덱스이다.

0부터 리스트가 시작하므로 b + 1 길이의 리스트를 만든다. 그리고 0과 1은 소수가 아니기 때문에 미리 False로 값을 변경한다.

📄 풀이

    m = int(n ** .5)
    for i in range(2, m + 1):
        if sieve[i] == True:
            for j in range(i * 2, b + 1, i):
                sieve[j] = False

    return [i for i in range(a, b + 1) if sieve[i] == True]

m, n = map(int, input().split())

print(*prime_list(m, n))

m은 n의 제곱근이다.

2부터 m까지 순회하면서 만약 소수라면(if sieve[i] == True:), i의 배수들을 모두 False 처리한다(for j in range(i * 2, b + 1, i):). for문의 세 번째 인자로 i를 넣어서 i 간격으로 탐색하도록 했다.

그렇게 한 후에 리스트 컴프리헨션으로 만든 리스트를 리턴한다. 백준의 채점에서 줄바꿈이나 띄어쓰기를 같은 개행문자로 보기 때문에 정답으로 출력된다.

📌 총평

에라토스테네스의 체! 매우매우 유용하다.