[백준] 1929번: 소수 구하기

Hint

1. 1부터 n까지의 숫자가 소수인지 아닌지 확인을 하고, 소수이면 그 숫자의 배수들은 소수일까요?
2. 소수의 배수들은 소수가 아닌게 확실하기 때문에 미리 제거해주면 나중에 소수인지 확인할 필요가 없다!
3. 에라토스테네스의 체 이용하기 (그게 뭐지?)

 

백준 1929번:  소수 구하기 (풀어보기)

import sys

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

# N까지의 숫자의 소수인지 아닌지에 대한 여부를 판단하는 배열 만들기
# 이것이 에레스토스테네스의 체! 
is_prime = [True] * (N+1)
is_prime[0], is_prime[1] = False, False

# 2부터 N까지의 숫자의 배수는 모두 소수가 아니라고 False로 바꿔주기
for i in range(2, N+1):     # 숫자
    for k in range(2, N+1): # 배수
        if i*k > N:
            break
        is_prime[i*k] = False

# M과 N 사이의 숫자 중 소수이면 출력하기
for num in range(M, N+1):
    if is_prime[num]:
        print(num)