1. 문제

출처: 백준 1929번 소수 구하기

2. 풀이

이전 문제들에서는 소수의 정의를 이용하여, 그때 그때 소수를 구해왔다.
그렇게 하면, 소수를 구해야 하는 소수 범위에 따라서 너무 많은 계산을 요구하게 될 수 있다.
따라서, 소수를 구할 때 미리미리 소수가 될 수 없는 숫자를 제거해두는 것이 용이하다.

해당 원리는 에라토스테네스의 체에서 확인해 볼 수 있다.
체에 숫자를 거르는 것처럼, 작은 소수부터 소수의 배수들을 소수 후보군에서 제거해나가면 된다.

코드에서는 해당 원리를 True, False 리스트를 활용하여 쉽게 구현할 수 있다.

3. 소스코드

M, N = map(int,input().split())

sieve = [False, False] + [True]*(N-1)
prime = []

for i in range(2,N+1):
    if sieve[i]:
        prime.append(i)
        for j in range(2*i,N+1,i):
            sieve[j] = False
            
for k in range(len(prime)):
    if prime[k] >= M:
        print(prime[k])

4. 그 외

처음에는 이전에 일일이 나눠주던 방식이 에라토스테네스의 체라고 생각하고 문제를 풀었다.
덕분에 아주 많은 "시간 초과"의 기록을 남기고, 정답률을 낮추는 데 기여할 수 있었다?...