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

1929번: 소수 구하기

 

---

문제

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

 

입력

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

출력

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

 

---

💻 코드

import sys
input = sys.stdin.readline

m, n = map(int, input().split()) # m부터 n까지의 소수 구하기
is_prime = [True] * (n + 1) # n+1 크기로 각 숫자가 소수인지를 판단하는 is_prime 배열

for i in range(2, int(n**(1/2))+1): 
  if is_prime[i]: #i가 소수이면 
      for j in range(i+i, n+1, i): #i의 배수를 소수가 아니라고 바꿈
        is_prime[j] = False
        
is_prime[1] = False # 1은 무조건 소수가 아님 

#출력
for i in range(m, n+1):
  if is_prime[i]: 
    print(i)

 

'에라토스테네스의 체' 알고리즘 설명을 그대로 구현하였습니다.

 

• n+1 크기로 각 숫자가 소수인지를 판단하는 is_prime 생성
• 2부터 루트n까지 반복문을 돌면서, (루트n을 사용하는 이유는 아래 에라토스테네스 체 설명 참고)
  • i가 소수이면 (is_prime[i]가 True이면)
  • i의 배수들을 모두 소수가 아니라고 바꿈 (is_prime[i]를 False라고 바꿈)
• is_prime 배열의 값이 True이면 소수인 것이므로 출력 

---

✏️ 풀이

에라토스테네스의 체

 

 

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

그림의 경우,

 

이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

 

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

---

⚠️ 잘못된 풀이 _ 시간초과

1차 시도

import sys
input = sys.stdin.readline

m, n = map(int, input().split()) # m부터 n까지의 소수 구하기
result = list(range(m, n))

for i in range(m, n):
  for j in reversed(range(2, i-1)):
    if i%j == 0 and i in result:
      result.remove(i)

print(*result, sep=" ")

• 그냥 보자마자 생각나는대로 풀었는데 사실 풀면서도 오 시간초과 나겠는데? 하면서 풀었다..
• 풀이 방법
  • m부터 n까지 정수로 이루어진 result 수열을 생성
  • 해당 숫자보다 작은 숫자로 나누었을 때 0이 되면 소수가 아니다 → 소수가 아니므로 result 수열에서 제거

 

2차 시도

import sys
input = sys.stdin.readline

m, n = map(int, input().split()) # m부터 n까지의 소수 구하기
is_prime = [True] * (n + 1)

for i in range(m, n):
  for j in range(2, i):
    if i%j == 0:
      is_prime[i] = False
      break
  if is_prime[i]:
    print(i)

• 시간을 좀 줄여볼 수 없을까 하다가 result 배열을 없애고 is_prime 배열을 만들어봤음 + break 문 추가
• 그래도 시간초과…. 이중반복문 부분이 문제인 것 같아서 '에라토스테네스의 체' 알고리즘을 공부하여 풀이했다.