[백준] 1929 소수 구하기 - 에라토스테네스의 체

[ 문제링크 ]

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

 

🚩 조건

1. 입력으로 M과 N이 들어옴
2. M이상 N이하의 소수를 모두 출력해라

 

 

🚩 접근, 시행착오

일단 2가 아닌 짝수이면 배제하고.. 홀수는 3부터 나눠가면서 소수인지 직접 확인?

이런 단순한 생각을 했는데 당연히 시간초과가 날 것 같았다..

그래서 결국 풀이를 찾아봤는데, 에라토스테네스의 체 알고리즘을 통해 소수를 구하는 문제였다.

 

에라토스테네스의 체는 어떤 정수 이하의 소수를 찾기 위해서, 소수를 찾는 것이 아니라 합성수를 제거하는 접근방식을 사용한다.

 

1. 정수 n이 주어지면, 2부터 n까지의 모든 수가 소수가 될 수 있다고 가정한다.

# 정답 출력 시 좀 더 편하게 하기 위해, 0과 1에 대해서 False로 설정함
is_prime = [False,False] + [True]*(N-1)

2. 2를 소수로 채택하고(=is_prime[2]를 True로 둠), 나머지 2의 배수를 모두 지운다(=is_prime[2의 배수]를 False로 둠).

3. 지워지지 않은 수(=is_prime[num]이 True) 중 가장 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.

4. 지워지지 않은 수 중 가장 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.

5. 위 과정을 n의 제곱근을 내림한 수를 만날 때까지 반복한다.

for num in range(2, int(N**0.5)+1) :

- 예를 들어 18의 경우, 1과 자신을 제외한 약수는 {2, 3, 6, 9}이고 제곱근은 4.2인데, 4.2보다 큰 6과 9 각각의 짝이 되는 약수 3과 2는 4.2보다 작으므로 제곱근보다 큰 수에 대해서는 체를 털어낼 필요가 없다.

- 근데 다른 코드들을 살펴보니 굳이 제곱근을 고려해서 반복하지 않고 단순하게 n까지 반복해도 되긴 하는 듯?

 

 

💻 코드 (Python)

# 에라토스테네스의 체

M,N = map(int, input().split())
is_prime = [False, False] + [True]*(N-1)

for num in range(2, int(N**0.5)+1) :
    if is_prime[num]:
        for composite in range(2*num, N+1, num):
            is_prime[composite]=False

for i in range(M, N+1):
    if is_prime[i]:
        print(i)