Baekjoon Online Judge 1929번 파이썬

문제 링크

잘못 짠 코드

import sys

M, N = map(int,sys.stdin.readline().split())

def prime_number(number):
  if number != 1:
    for i in range(2,number):
      if number % i == 0:
        return False
  else:
    return False
  return True
  
for i in range(M, N+1):
  if prime_number(i) == True:
    print(i)

직전의 문제와 비슷해서 비슷하게 풀었는데 시간 초과가 나왔다.
다른 사람들의 질문을 보니 ‘에라토스테네스의 체’를 이용하면 시간을 줄일 수 있다고 한다.

num**0.5을 하는 이유는 모든 약수들은 대칭 형태를 가지고 있기 때문이다. ( 8 = 4 * 2 = 2 * 4)

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

에라토스테네스의 체 - 나무위키

정답 코드

import sys
import math

def isPrime(num):
  if num == 1:
    return False
  else:
    for i in range(2, int(num**0.5)+1):
      if num % i == 0:
        return False
    return True

M, N = map(int,sys.stdin.readline().split())
numbers = []

for i in range(M,N+1):
  if isPrime(i):
    print(i)