소수의 판별, 에라토스테네스의 채 (2021/02/16)

소수

 

소수란 2보다 크면서 1과 자기자신을 제외한 수로 나누어 떨어지지 않는 수이다.

 

ex) 2, 3, 5, 7, 11, ...

 

1. 소수를 구하기 위해선 x를 2부터 x-1까지 나누어보고 나누어 떨어지는지 확인한다. 만약 나누어 떨어지면 소수가 아니다.

 

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

-> 이 경우에, 2부터 x-1까지 다 확인을 해야하므로 시간복잡도가 높다. O(X)

 

2. 1에서 소수를 구한 방법처럼 2부터 x-1까지 모두 확인할 필요가 없다.

 

3. 숫자 16의 경우에 약수는 1, 2, 4, 8, 16이다. 이 경우에 2x8과 8x2 모두 16이므로 대칭이다. 특정한 자연수 x가 소수인지 확인하기 위해서는 가운데 약수까지만 확인하면 된다. 숫자 16의 경우에 16의 제곱근인 4까지만 확인하면 된다.

 

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

 

4. 제곱근까지만 구함으로써 시간복잡도가 O(X) ->O(X^1/2)로 감소했다.

 

 

에라토스테네스의 채

 

에라토스테네스의 채는 소수를 판별하는 대표적인 알고리즘이다.

 

구하는 방식은

 

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

2. 남은 수 중에서 가장 작은 수를 찾고 그 수를 제외한 수의 배수를 제거한다.

3. 2를 반복한다.

 

(여기서도 N의 제곱근까지만 확인하면 된다.)

 

import math
n=100
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=' ')

 

4. 에라토스테네스의 채를 이용하여 소수를 구함으로써 시간복잡도를 낮출 수 있다. O(NloglogN)

5. 그러나 메모리를 많이 필요로 한다는 단점이 있다.