[백준/파이썬] 1929번: 소수 구하기

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

문제 풀이 과정

이전 포스팅에서 다뤘던 백준 1978번 문제가 소수를 찾아서 소수가 총 몇 개인지를 찾아내는 문제였어서 이번에도 소수를 구하는 문제를 풀려고 이 문제를 골라서 하게 되었다. 같은 알고리즘으로 문제를 풀면 되겠지 했으나, 이 문제는 매우 많은 수의 소수를 구해야할 뿐 아니라 범위마저 넓어서 기존의 소수 구하는 코드로 테스트 해보니 시간 초과가 발생했다...

# 시간초과 코드
M, N = map(int, input().split())

primes = []

for num in range(M, N+1):
    for i in range(2, num+1):
        if (num % i == 0):
            if (num == i):
                primes.append(i)
            break

for i in primes:
    print(i)

이 방법이 계속 실패했던 이유는 이번 문제에서의 수의 범위가 1000000까지 인데, 매 번 O(n^2)의 시간 복잡도로 모든 수를 처음부터 끝까지 검사하고 있으니 도저히 답을 구하지 않아서 생기는 시간초과였다.
 
이 문제를 그렇다면 어떻게 해결할 수 있을까 고민하던차 방대한 범위 내에서 대량의 소수들을 판별하여 낼 필요가 있을 때 사용하는 방법으로 에라토스테네스의 체 알고리즘이 있다는 것을 알게 되었다.

에라토스테네스의 체

https://velog.io/@max9106/Algorithm-에라토스테네스의-채

[Algorithm] 에라토스테네스의 체

나는 이 알고리즘에 대해 이해할 때 위의 블로그글을 참고했다. 에라토스테네스의 체 실습 코드는 C언어로 되어있었으나, 개념을 이해하는 데에는 전혀 문제가 없었고, 다른 위키백과나 긴 개념 설명이 있는 블로그들보다 훨씬 간단하게 이해할 수 있었다.
 
내가 이 문제를 풀때는 인지하고 있지 않았었는데, 어떤 하나의 숫자에 대해서 소수인지 아닌지를 판별할 때에는 2부터 그 숫자의 제곱근까지의 숫자만 약수 여부를 파악하면 된다고 한다. 그도 당연할 것이, 상식적으로 생각해보아도 만약 내가 10이 소수인지 아닌지 판별하고자 할 때 10의 제곱근을 계산해보면 3.xx가 나올텐데 10은 2와 5의 곱이므로 10의 제곱근보다 작은 값이 약수에 포함되게 된다. 이처럼 몫과 나누는 수, 둘 중 하나는 반드시 판별하고자 하는 수의 제곱근 값보다는 작게 되므로, 더 빨리 소수 판별을 할 수 있게 된다. 내가 이 문제를 풀때는 이 원리를 적용하지 않았지만, 내가 푼 코드에 이 원리를 적용해서 개선한다면, 더 빨리 문제를 풀 수도 있을 것 같다는 생각이 든다.
 
이 문제를 푼 코드의 알고리즘(에라토스테네스의 체)은 다음과 같다.
먼저 M과 N 사이의 숫자들 중에서 소수인 숫자들을 작은 순서대로 출력하는 것이 문제였기 때문에 M과 N의 값을 받아주고, 1부터 N까지의 수들을 딕셔너리 타입으로 저장시켜 주었다. 
{1:1, 2:2, 3:3, ... , N:N} 이런 식으로
왜 M부터 안하고 1부터 딕셔너리를 지정해주는 가 물어본다면, 나중에 2부터 시작하는 배수들을 하나씩 다 제거해나갈건데, 1부터 딕셔너리가 시작하지 않으면 존재하지 않는 딕셔너리 키값으로 자꾸 밸류값을 물어보기 때문에 에러가 발생한다. (나도 처음에 이 에러 때문에 실패했다) 따라서 1부터 딕셔너리를 입력하는 것이다. 이처럼 딕셔너리를 지정해주었다면 새로운 반복문을 이용해서 범위 내의 i 배수에 겹치는 수들을 모두 제거해나간다. 여기서의 제거라 함은 Key, Value 값이 서로 동일하게 지정되어 있는 상태에서 Value값을 0으로 수정해주는 것이다. 그렇게 하면, 나중에 소수들만 출력할 때 Value가 0인 값들을 제외하는 식으로 출력해줄 수 있다.
 
세부적인 정답 예시 코드는 아래와 같다. 에라토스테네스의 체 알고리즘의 플로우를 생각하며 코드를 이해해보면 좋을 것 같다.

정답 예시 코드 (Python)

M, N = map(int, input().split())

nums = {}

for i in range(1, N+1):
    nums[i] = i

for i in range(2, N+1):
    # 이미 지워진 숫자면 넘어가기
    if (nums[i] == 0):
        continue
    # i의 배수인 수들은 전부 없애기 (본인 제외: 본인은 소수이기때문)
    for j in range(i+i, N+1, i):
        if (j % i == 0):
            nums[j] = 0

for i in range(M, N+1):
    if (nums[i] != 0 and i != 1):
        print(i)