[Python] 소수 찾기 알고리즘(에라토스테네스의 체)

소수(Prime Number)

1과 자기 자신만을 약수로 가지는 수

※그러므로 1은 소수가 아님

 

방법 1 - O(n)

for i in range(2, n):
	if n % i ==0:
    	return False
    return True

소수 = 1과 자기 자신만을 약수로 가진다.

        = 수를 나누었을 때 1과 자기 자신만으로만 나누어 떨어질 수 있다.

→ 이 알고리즘은 2부터 n-1 까지 연산하는 for문이 필요하다.

시간복잡도 = O(n)

 

방법 2 - O(2/n)

for i in range(2, int(math.sqrt(n))+1):
	if n % i == 0:
    	return False
    
    return True

굳이 약수를 2부터 n까지 나누지 않더라도 계산할 수 있는 방법이 있다.

예를 들어 12의 약수를 보면, 1 2 3 4 6 12 가 있다. 3과 4를 기준으로 약수는 *(곱셈)으로 대칭되고 있다. 그래서 한 쪽만 알고 있더라도 다른 한 쪽을 알아낼 수 있다.

[1, 12] [2, 6] [3, 4] 이렇게 묶일 수 있는데,  3은 1.73.. 으로 3 < √4 이다.

따라서 만약 n이 소수가 아니라면 √12 전에 3이나 4같이 12의 약수가 등장한다는 것을 이용한 것이다. (처음에는 이해를 못했는데 어쩌면 당연하다. √12 전에 √4가 나타나고, √3이 나타날 것이다..)

근데 루트는 사실상 이해도 어렵고, 복잡한 계산에 들어가면 결국 수학문제로 바뀔 것이기 때문에 간단하게 제곱근으로 계산하기로 한 분위기이다. 그래서 i*i <= n 이 되는지를 확인한다.

 

에라토스테네스의 체

지금까지는 한 개의 수에 대해서 효율적으로 소수인지 찾아내는 방법에 대해 알아보았다. 하지만 여러 개의 수를 계산하려고 하면 함수를 여러번 돌리고, 상당히 번거로울 것이다. 그래서 등장한 것이 에라토스테네스의 체이다.

n = 100
arr = [True for i in range(n+1)] #2부터 n까지 모든 수를 대상으로 True 처리

for i in range(2, int(math.sqrt(n))+1):
	if arr[i] == True:  #i가 소수일 때
    	j=2 #i만 남기려고 j는 2부터 곱해준다
        while i*j <= n:
        	arr[i*j] = False #i의 배수를 모두 지워준다
            j+=1

print(arr)

에라토스테네스의 체, 위키백과

1. 2부터 n까지의 모든 자연수를 나열한다.

2. 나열된 숫자 중 가장 작은 수를 x로 지정한다.

3. 나열된 숫자 중 x는 놔두고, x의 배수를 제거한다.

4. 더 이상 반복할 수 없을 때까지 2번과 3번을 반복한다.

방법은 매우 간단하지만, 속도가 정말 빠르다. 기존의 방법들보다 더 빠르니, 이 방법을 쓰는 것을 추천한다.