[Python] 백준 #1929- 소수 구하기

문제

1929번: 소수 구하기

---

코드

---

My answer

import sys
import math
input = sys.stdin.readline

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

array = [1 for i in range(m+1)]

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

Another answer

M,N=map(int,input().split())
*s,=range(N+1)
for i in s[2:]:
    if s[i]:
        s[2*i::i]=[0]*(N//i-1)
        if(i>=M):
        	print(i)

풀이

---

이 문제는 전형적인 소수 구할 때 쓰는 방법인 에라토스테네스의 체를 이용하여 푸는 방법이다. 대부분의 소수문제는 이 방법을 이용하면 된다. 에라스토스테네스의 체 알고리즘이 가장 메모리를 적게이용하면서 풀 수 있다. 이 알고리즘을 이용하지 않으면 각 수마다 일일이 약수의 갯수를 구해서 소수인지를 판별하는 멍청한 짓을 하게된다. 에라토스테네스의 체를 잘 모르면 알고리즘 카테고리에 작성해놓았으니 확인바랍니당. (1은 소수가 아니라는 걸 잊으면 안됩니다.)

Algorithms-[Euclidean algorithm & The Sieve of Eratosthenes ]