[백준] 1929번 [기본수학2] 소수 구하기

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

나의 풀이1

n,m = map(int,input().split(" "))
nlist = [True for _ in range(1,m+2)]
for i in range(2,m+1):
    if nlist[i]:
        for j in range(i*2,m+1,i):
            nlist[j] = False

for i in range(n,len(nlist)):
    if nlist[i] and i > 1:
        print(i)

에라토스테네스의 체를 이용하여 일정 범위내 수열에서 배수들을 제거해 소수만 남겨서 마지막에 출력을 해주었습니다.

나의 풀이2

m,n = map(int,input().split(" "))
list = []
for i in range(m,n+1):
    loop = True
    for j in range(2,int(i**(1/2))+1):
        if i % j == 0 and i != j:
            loop = False
            break
    if loop and i!=1:
        list.append(str(i))

print("\n".join(list))

16의 약수: [1, 2, 4, 8 16] 해당 수를 살펴보면 가운데 수를 기준으로 대칭적으로 곱을 통해 16을 만들 수 있다. 이를 통해, 소수의 절반에 해당하는 제곱근까지만 살펴보면 소수 판별이 가능하다는 것을 알 수 있다. 이를 이용한 풀이입니다.

에라토스테네스 체란?

에라토스테니스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법입니다. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부릅니다. 특정 숫자의 배수는 소수가 아니라는 법칙에 착안하여 2 ~ N까지의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않은 숫자를 소수로 판별하는 방식이며 일종의 노가다 방식이라 상당히 무식한 방법이지만 이 방식이 프로그래밍에서는 상당히 효율적인 방법론이 됩니다. 에라토스테네스의 체는 반대로 2부터 배수들을 지워나가는 방식이기 때문에 숫자마다 일일이 약수가 있는지 검사할 필요가 전혀 없고, 이미 지워진 숫자는 바로 건너뛰면 되니 실행시간이 매우 짧습니다.