[Algorithms/Python] 에라토스테네스의 체

일정 범위 내의 소수를 모두 찾는 알고리즘이다. 여기서 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 갖는 수이다.

자연수 n이 소수인지 아닌지를 판별하기 위해서는 단순히 2부터 n-1까지 반복하면서 나누어 떨어지는지 확인하면 된다. 하나라도 나누어 떨어지는 수가 존재한다면 1과 자기자신을 제외한 수 중 약수를 갖게 되는 것이므로 n은 소수가 아니다.

def is_prime_number(n):
    for i in range(2,n): # 2부터 n-1까지
        if n % i == 0: # 하나라도 나누어 떨어지는 수가 있다면
            return False # 소수가 아니다.
	
    return True

약수를 판단하는 데에는 기본적으로 2부터 n-1까지 모두 반복할 필요가 없다. 각 수가 갖는 약수는 해당 수의 제곱근을 기준으로 대칭을 이루기 때문이다. 16의 경우 1,2,4,8,16의 약수를 갖고 16의 양의 제곱근인 4를 기준으로 대칭을 이룬다. 즉, 16이 2로 나누어 떨어짐을 알게 된다면 8로 나누어 떨어지는 건 자동적으로 참이다. 16을 2로 나눈 몫이 8이기 때문이다.

위 사실을 이용하면 n이 소수임을 판단하기 위해서는 2부터 n의 제곱근까지 나누어 떨어지는지만 확인하면 된다. 이 경우 n이 소수를 판별하는 데에 시간복잡도는 O(√n)이 된다.

def is_prime_number(n):
    end = int(n**(1/2))
    for i in range(2, end+1):
        if n % i == 0:
            return False
    
    return True

다음으로는 일정 범위 내의 소수를 모두 찾을 때, 효율적으로 할 수 있는 방법으로 에라토스테네스의 체를 알아보자. 하나의 수가 소수인지 확인하는 것은 O(√n)의 시간복잡도가 걸리고 일정 범위 내의 소수를 모두 찾기 위해서는 그것을 n번 또 반복하게 된다. 하지만 제곱근까지만 확인해서 그 제곱 수는 모두 체크해주는 방식으로 한다면 최대 O(n√n)의 시간복잡도로 모두 알 수 있다.

def prime_numbers(n):
	arr = [i for i in range(n+1)]
    end = int(n**(1/2))
    for i in range(2, end+1):
    	if arr[i] == 0:
        	continue
        for j in range(i*i, n+1, i):
        	arr[j] = 0
     return [i for i in arr[2:] if arr[i]]