9. 기타 알고리즘: 소수 판별, 에라토스테네스의 체 알고리즘

소수: 1보다 큰 자연수 중에서 1과 자신을 제외한 자연수로는 나누어 떨어지지 않는 수

 

이걸 코드로 그대로 옮기면

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

이렇게 간단하게 쓸 수 있다

 

숫자가 X일 때 시간복잡도는 O(X)가 된다

 

여기서 약수의 성질을 이용하면 시간복잡도를 줄일 수 있다

모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다

예를 들어 16의 약수는 1, 2, 4, 8, 16인데,

1*16=16, 2*8=16으로, 4를 기준으로 대칭이다

따라서 특정한 자연수의 모든 약수를 찾을 때, 가운데 약수(제곱근)까지만 확인하면 된다

이것을 소수판별 알고리즘에 적용시키면

import math

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

i를 2부터 x의 제곱근까지만 증가하게 할 수 있다

시간복잡도가 O(N^(1/2))가 된다

---

다수의 소수 판별

 

특정 범위 안에 존재하는 모든 소수를 찾아야 할 때는

에라토스테네스의 체 알고리즘을 사용하는 것이 효율적이다.

 

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

2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.

3. 남은 수 중에서 i의 배수를 모드 제거한다(i는 제거하지 않는다).

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

 

import math
n=1000
array=[True for i in range(n+1)]

for i in range(2,int(math.sqrt(n))+1):
    if array[i]==True: #남은 수 중 가장 작은 수
        j=2
        while i*j<=n: #그 수의 배수를 모두 제거
            array[i*j]=False
            j+=1

#모든 소수 출력
for i in range(2,n+1):
    if array[i]:
        print(i,end=' ')

시간복잡도가 O(NloglogN)으로 매우 빠르다.

다수의 소수를 찾을 때 유용하지만,

배열에 소수 여부를 저장해야 하므로 메모리가 많이 필요하게 된다