[백준 1929] 소수 구하기 - 에라토스테네스의 체

코드

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

arr = [0 for _ in range(n+1)]
arr[0] = 1
arr[1] = 1

for i in range(2, n+1):
    mul_num = 2
    while i*mul_num <= n:
        arr[i*mul_num] = 1
        mul_num += 1

for idx, num in enumerate(arr):
    if num == 0 and idx >= m:
        print(idx)

 

설명

• 제곱근 까지만 검사하는 코드를 넣었는데 시간초과가 떠서 에라토스테네스의 체로 해결
• 0이 n개만큼 있는 배열을 선언한 뒤, 2~n의 배수에 해당하는 idx의 수만 1로 수정
• m보다 큰 idx를 가지고 있고, 해당 idx 위치의 수가 0이면 출력