백준 1929번 [Python] 문제풀이(소수 구하기) - 이정개

문제

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

 

 

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000)

 

 

출력

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

 

 

예제 입력 1

3 16

 

 

예제 출력 1

3
5
7
11
13

 

 

알고리즘 분류

ㆍ에라토스테네스의 체

 

 

파이썬 코드(시간초과)

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

def isPrime(x):         # 소수를 판별하는 함수
  if(x<2):              # 1은 소수가 아니므로 False
    return False
  for i in range(2,x):
    if(x%i==0):	        # 2부터 주어진 수x 사이의 수로 x가 나누어떨어지면 False
      return False
  return True           # 1과 자기자신만으로 나누어 떨어지므로 소수

for i in range(m, n+1): # m부터 n까지 소수를 하나하나 찾음
  if(isPrime(i)):
    print(i)

가장 먼저 떠올린 생각은 m과 n사이의 숫자 하나하나를 직접 확인하는 방법.

하지만 높은 확률로 시간 초과라는 결과가 나오게 된다.

원인은 m과 n의 범위에 따라 늘어나는 연산시간.

1부터 1,000,000사이의 수를 하나하나 확인하려니 시간초과가 나오지 않는 것이 더 이상하다.

 

 

파이썬 코드(성공)

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

def isprime(m, n):
  n += 1                            # for문 사용을 위한 n += 1
  prime = [True] * n                # n개의 [True]가 있는 리스트 생성
  for i in range(2, int(n**0.5)+1): # n의 제곱근까지만 검사
    if prime[i]:                    # prime[i]가 True일때
      for j in range(2*i, n, i):    # prime 내 i의 배수들을 False로 변환
        prime[j] = False

  for i in range(m, n):
    if i > 1 and prime[i] == True:  # 1 이상이면서 남은 소수들을 출력
      print(i)

isprime(m, n)

시간을 줄이는 방법은 여러가지가 있지만

문제에 제시되어있는 에라토스테네스의 체를 활용하기로 하였다.

 

에라토스테네스의 체란 간단히 설명하자면 일정 범위내 수열에서 배수들을 제거해 소수만 남기는 방법이다.

ex) 수열 [2 3 4 5 6 7 8 9 10] 에서 2의 배수 제거

=> [2 3 5 7 9] 에서 3의 배수 제거

=> [2 3 5 7]

요약하면 말그대로 체로 걸러서 소수만 남기는 게 핵심

 

이처럼 문제를 제대로 확인 안하면 한문제로 두번 코딩하게 된다.

다음부터는 꼼꼼히 확인하자.