[알고리즘 in python] 소수(Prime Number) 구하기 / 에라토스테네스의 체

소수 (Prime Number) 란?

• 1과 자기 자신 외에는 다른 약수를 가지지 않는 자연수.
• 1보다 큰 자연수 중에서 오직 두 개의 약수만을 가지는 수 -> 1은 소수가 아님

---

 

소수 판별 알고리즘

• 특정 숫자 n이 소수인지 확인하려면 2부터 $\sqrt{n}$ 까지의 모든 숫자로 n을 나누어 본다.

$n=a \times b$

이 때 a와 b 둘 중 하나는 반드시 n의 제곱근 이하이다.

n이 소수가 아니라면, 반드시 두 약수 중 하나는 $\sqrt{n}$ 이하가 되게 된다.

따라서 소수인지 판별하기 위해서는 2부터 n-1 까지가 아니라, $\sqrt{n}$ 까지만 확인하면 된다.

 

# 제곱근 계산 위해 math 모듈 사용
import math

def ifPrime(n):
	# 2부터 n의 제곱근까지 반복
	for i in range(2, int(math.sqrt(n))+1):
    	# 나누어 떨어지면 소수가 아님
    	if n % i == 0:
        	return False
    # 어떤 수로도 나누어 떨어지지 않으면 소수임
    return True

---

 

에라토스테네스의 체

• 주어진 범위 내의 숫자들에서 소수를 걸러내기 위해, 소수의 배수를 제거하는 방식.
• 시간 복잡도 : $O(n\log\log n)$ 으로 매우 효율적
• 탐색해야 하는 수가 클 때 사용하자

def eratos(n):
	# n 까지의 모든 수가 소수라고 가정하고 초기화
    is_Prime = [True] * (n+1)
    p = 2
    # n의 제곱근까지만 탐색
    while p ** 2 <= n:
    	# is_Prime[p]가 True라면, p는 소수
        if is_Prime[p]:
        	# 소수의 배수를 False 처리
        	for i in range(p**2, n+1, p):
            	is_Prime[i] = False
        p += 1

	# is_Prime[p]
	prime_nums = [p for p in range(2, n+1) if is_Prime[p]]
    return prime_nums

 

 

참고 : ChatGPT