[백준] 1929번 소수 구하기

링크 : https://www.acmicpc.net/problem/1929

문제

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

풀이

첫번째 시도 : 통과는 했지만 너무 오래 걸림

import sys
input = sys.stdin.readline

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

array = []
for i in range(m, n+1):
    # 1은 소수가 아니므로 예외 처리
    if i == 1:
        continue
    # flg 변수가 없으면 for  j 문이 break 되더라도 print(i)가 발생함
    flg = 0
    for j in range(2, int(i**0.5)+1):
        if i%j == 0:
            flg = 1
            break
    if flg == 0:
        print(i)

두번째 시도 : 에라토스테네스 체 활용

에라토스테네스 체란 쉽게 말하면 루트n보다 작은 소수들의 배수를 체로 걸러낸다는 뜻이다. (소수 자신은 남겨둠)

예를 들어, 20이라는 수에 에라토스테네스 체를 활용하면 루트20 < 5이므로 5까지만 걸러낸다

• 2의 배수를 걸러냄 : [2,3,5,7,9,11,13,15,17,19]
• 3의 배수를 걸러냄 : [2,3,5,7,11,13,17,19]
• 5의 배수를 걸러냄 : [2,3,5,7,11,13,17,19]

import sys
input = sys.stdin.readline
m, n = map(int, input().split())

def is_prime(m,n):
    n += 1
    flg = [True] * n
    for i in range(2, int(n**0.5)+1):
        if flg[i] == True:
            for j in range(i*2, n, i):
                flg[j] = False

    for i in range(m,n):
        if i>1 and flg[i] == True:
            print(i)

is_prime(m,n)