[백준 - 1929] 소수 구하기

koyo·2020년 9월 24일
0

백준

목록 보기
1/13
post-thumbnail

문제

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

문제해설

에스토스테네스의 체를 활용하자!

범위에 대한 소수를 찾는 것에는 이전에 계산한 결과를 활용할 수 있는 에스토스테네스의 체를 활용하는 것이 좋다. 하지만 범위가 1,000,000이 넘는다면 주의해야한다. 해당문제는 범위 안이므로 가능하다.

import math

m, n = map(int, input().split())
array = [True for _ in range(n+1)]

for i in range(2, int(math.sqrt(n))+1):
    if array[i] == True:
        j = 2
        while i * j <= n:
            array[i * j] = False
            j += 1

for i in range(m, n+1):
    if array[i] == True:
        print(i)
profile
클라우드 개발자가 될 코요입니다.

0개의 댓글