백준 - 단계별 문제풀기(1978번)

1929번

import sys
input = sys.stdin.readline
s = []

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

for i in range(m, n+1):
    condition = True
    if i == 1:
        continue
    for j in range(2, int(i**0.5) + 1):
        if(i % j == 0):
            condition = False
            break
    if condition:
        prime_num.append(i)
print(*prime_num, sep='\n')

• 에라토스테네스의 체 활용.
• 에라토스테네스의 체란 간단히 설명하자면 일정 범위내 수열에서 배수들을 제거해 소수만 남기는 방법이다.
  ex) 수열 [2 3 4 5 6 7 8 9 10] 에서 2의 배수 제거
  => [2 3 5 7 9] 에서 3의 배수 제거
  => [2 3 5 7]
  요약하면 말그대로 체로 걸러서 소수만 남기는 게 핵심