[정수론]소수구하기, 에라토스테네스의 체

✏️소수 : 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수, 1과 자기 자신 외에 약수가 존재하지 않는 수

📝소수를 구하는 대표적인 판별볍인 에라토스테네스의 체

⭐️원리

1. 구하고자 하는 소수의 범위만큼 1차원 리스트를 생성한다.
2. 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우 현재 선택된 숫자의 배수에 해당하는 수를 리스트에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다.
3. 리스트의 끝까지 2를 반복한 후 리스트에서 남아있는 모든 수를 출력한다.

⭐️시간 복잡도

이중 for문을 이용하므로 시간 복잡도가 O(N^2)라고 판단할 수 있고 실제 시간 복잡도는 최적화의 정도에 따라 다르겠지만 O(Nlog(log(N))이다. 그 이유는 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 비넙ㄴ하게 발생하기 때문이다.

⭐️N의 제곱근까지만 탐색하는 이유

N의 제곱근이 n일 때 N = a * b 를 만족하는 a와 b가 모두 n보다 클 수 없다. a가 n보다 크면 b는 n보다 작아야 한다. 즉, N보다 작은 수 가운데 소수가 아닌 수는 항상 n보다 작은 약수를 가진다.

소수구하기 / BOJ 1929

import math
M, N = map(int, input().split())
A = [i for i in range(N+1)] 			# 각각의 인덱스값으로 초기화
print(A)
for i in range(2, int(math.sqrt(N))+1): # 제곱근까지만 수행
    if A[i] == 0:
        continue
    for j in range(i+i, N+1, i): 		# 배수 지우기
        A[j] = 0

for i in range(M, N+1):
    if A[i] != 0:
        print(A[i])