백준 - 1929. 소수 구하기 (MJ)

#1929. 소수 구하기

백준의 실버3티어문제이다.

📖Problem

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

입력

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

출력

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

예제 입력 1

3 16

예제 출력 1

3
5
7
11
13

🔍Approach

지난 시간에 소수 구하면서 배웠던 ‘에라토스테네스의 체’를 바로 적용해보았다.

에라토스테네스의 체 알고리즘

출처 : https://loosie.tistory.com/267

• 에라토스테네스의 체 알고리즘은 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘이다

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

구현

• 지워지지 않은 수를 찾을 때 n이 아니라 $n^{1/2}$까지만 찾는다. 이것은 위의 소수 판정 알고리즘과 똑같은 최적화 방식이다.
• 또한, i의 배수들을 모두 지울 때 $i^2$에서 시작하는 것이 아니라 $i^i$에서 시작하는 것이다. $2^i$는 이미 2의 배수를 지울 때 지워졌고 $3^i$는 이미 3의 배수를 지울 때 지워졌기 때문이다.
  • $i^k$ (k < i)까지는 이미 검사되었으므로 j시작 값은 $i^2$에서 $i^i$로 개선할 수 있다. (k의 최댓값은 i-1이므로)
• 만약 isPrime[i]가 true이면, i 이후의 i 배수는 약수로 i를 가지고 있는 것이 되므로 모두 true값을 준다.
• 만약 isPrime[i]가 false이면, i는 이미 소수가 아니므로 i의 배수 역시 소수가 아니게 된다. 그러므로 검사할 필요가 없다.

import math

n = 1000 # 2부터 1000까지의 모든 수에 대하여 소수 판별
array = [True for i in range(n + 1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제와)

# 에라토스테네스의 체 알고리즘
for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
    if array[i] == True: # i가 소수인 경우(남은 수인 경우)
        # i를 제외한 i의 모든 배수를 지우기
        j = 2
        while i * j <= n:
            array[i * j] = False
            j += 1

# 모든 소수 출력
for i in range(2, n + 1):
    if array[i]:
        print(i, end=" ")

• 시간복잡도 : O(NloglogN)
• 메모리가 많이 필요하다는 단점

My submission

🚩첫 코드

→ 에라토스테네스의 체 구현 방식을 그대로 가져옴

import math
m, n = map(int, input().split())
primer = [True for i in range(n + 1)] 

for i in range(2, int(math.sqrt(n)) + 1):
    if primer[i] == True: 
        j = 2
        while i * j <= n:
            primer[i * j] = False
            j += 1

for i in range(m, n + 1):
    if primer[i]:
        print(i)

이렇게 했을 때 출력 결과는 정상적으로 작동한다. 하지만 백준에서는 틀렸다고 나왔다.

🚩최종 제출

• m, n을 입력받는다. primer리스트에는 초기에 모든 소수가 소수(True)인 것으로 초기화를 한다.
• 2부터 n의 제곱근까지의 모든 수를 확인한다.
  • i가 소수인 경우에 두번째 for문을 이용해서 i를 제외하고 i의 모든 배수를 지운다.
  • 이는 True를 False로 바꿔줌으로서 지울 수 있다.
• i가 1보다 크고 primer에 있는 값이 소수(True)일 때 출력한다.

m, n = map(int, input().split())
primer = [True] * (n + 1) # 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제와)

for i in range(2, int(n**0.5) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
    if primer[i]: # i가 소수인 경우(남은 수인 경우)
        # i를 제외한 i의 모든 배수를 지우기
        for j in range(2*i ,n+1, i):
            primer[j] = False
# 입력받은 범위 m, n 사이에 있는 소수 출력
for i in range(m, n + 1):
    if i > 1 and primer[i] == True:
        print(i)

💡Retrospect

• 막상 문제 푸는데 그냥 풀려니까 시간초과가 뜨고 잘 풀리지 않았다. 그래서 저번에 풀었던 신기한 소수 문제에서 에라토스테네스의 체에 대해서 조사한 부분을 다시 복습하며 풀게 되었다. 덕분에 이전 개념을 다시 되짚어볼 수 있어서 좋았다.
• 에라토스테네스를 그대로 복사해서 날먹하려고 했으나…. 수많은 변경과 시도 끝에 백준에서 맞았다고 나오게 되었다…