[파이썬] 단계별 백준 문제 풀기 - 1929 기본수학 (소수구하기)

 

문제

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

입력

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

출력

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

 

---

<<코드>>

import math #math 모듈 삽입 -> sqrt() 함수 사용 위함

#소수 구하는 함수 정의
def prime(n):
  if n==1: #n이 1이면 소수가 아니니까 false 반환
    return False
  # n의 제곱근보다 +1 까지만 for문 반복
  else:
    for i in range(2,int(math.sqrt(n))+1): 
      if n%i ==0: #나머지가 0이라면 약수가 존재함. 고로 소수가 아니다
        return False
    return True #그 외는 다 소수!! true 로 반환

# M과 N 두 수가 주어진다면, N+1까지 범위에서 소수 함수를 돌려 소수만 출력해준다 
M,N = map(int, input().split())
for i in range(M,N+1):
  if prime(i):
    print(i)

 

<<결과값>>

$ python main.py
3 16
3
5
7
11

 

---

문제가 짧다고 방심했다. 소수? 중학교때 배운거 아닌가? 라고 접근했다가 아주 두들겨 맞았다... (｡•́︿•̀｡) 

에라토스테네스라는 고대 그리스의 수학자의 '에라토스테네스의 체' 로 접근해야한다.... (이걸 어떻게 아냐구요 흑)

주어진 범위에서, 2를 제외한 2의 배수를 제거하고, 3을 제외한 3의 배수를 제거하고, 5를 제외한 5의 배수를 제거하고 남은 수가 바로 소수이다.

(그의 식에서는 7의 배수도 지우지만 여기선 7을 남겨두고 7의 배수는 지울 필요 없다. 어차피 2,3,5의 배수에서 걸러진다) 

 

이 문제의 포인트는 시간을 줄이는 것이다.

시간을 줄이려면 for문을 통해 n까지 반복하지말고 n의 제곱근까지만 반복한다.

Because 모든 약수는 대칭을 이룬다.

가령 16의 약수는 1,2,4,8,16 인데, 4까지만 지우면 8과 16은 2의 배수에서 이미 제거되서 떨어져나간다. 굳이 4 이상은 볼 필요 없다는 것!! 

 

예를들어 20의 경우도 20의 제곱근은 4.xxx가 될 것이다. +1를 더해서 5까지만 돌려준다. 20의 약수 중 5 이상의 10, 20은 진작에 지워지기 때문

 

 

 - sqrt(N) : N의 제곱근 반환

 - 소수는 2,3,5,7로 나누어지지 않은 수 (1과 자기 자신만을 약수로 갖는 수)

 - for문을 효율적으로 돌리기 위해 range를 제곱근까지만 정해주는 것*

 

 

에라토스테네스의 체: 링크참고