[소수의 판별] 백준 1929번 '소수 구하기' (Python)

<문제 링크>

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

---

<문제 풀이>

• N과 M의 최댓값이 1,000,000이므로 에라토스테네스의 체 알고리즘으로 풀어야 함

<코드>

'''입력 예제
3 16
'''

import math
n,m = map(int,input().split())
array = [True for i in range(m+1)]
array[0],array[1] = 0,0   #0,1은 소수 아님 주의

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

for i in range(n, m + 1):
    if array[i]:
        print(i)

 

<고쳐야 할 점>

• 에라토스테네스의 체 알고리즘 기억하기
• 0과 1은 소수가 아님 주의