[Algorithm] Prime number - 에라토스테네스의 체

Prime Number

---

소수(Prime number)란 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다.

정수론의 기본 정리에 따라, 모든 자연수는 단 한 가지 방법의 소수의 곱으로 표현할 수 있다.

 

 

소수 찾기

---

어떤 정수 n이 소수인지 판별하는 방법에는 여러 가지가 있다.

먼저 소수의 정의에 따라 2부터 n-1까지 모든 수로 나누었을 때 나누어 떨어지는 수가 없다면 n은 소수이다.

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

하지만 위의 경우 n-1까지 모든 수를 확인해야하므로 시간 복잡도가 \( O(n) \)이 된다.

 

연산의 횟수를 줄이기 위해 \( n/2 \)까지의 숫자만 확인하는 방법도 있지만 해당 방법 또한 시간 복잡도는 \( O(n) \)이다.

조금 더 효율적인 방법으로 \( \sqrt{n} \)까지 확인하는 방법이 있다. n이 소수가 아닌 합성수라면 어떤 두 수의 곱으로 표현될 때 항상 한 수는 \( n^{1 \over 2} \) 이하, 다른 한 수는 \( n^{1 \over 2} \) 이상이기 때문에 해당 수의 제곱근까지만 확인하도록 최적화할 수 있다.

 

이 외에도 2와 3을 제외한 소수는 \(6k \pm 1\)의 형태라는 사실을 이용하는 방법 등이 있다.

 

 

에라토스테네스의 체

---

위의 방법들은 하나의 숫자가 소수인지 판별할 수 있다.

만약 여러 개의 수에 대해서 소수를 판별해내려면 모든 수에 대해 위의 방법을 적용해야 하기에 상당한 시간이 소요된다. 이때 사용할 수 있는 방법이 바로 에라토스테네스의 체이다. 에라토스테네스의 체는 특정 범위 내에서 모든 소수를 판별해내기 위한 효율적인 방법이다.

 

알고리즘

1. 2부터 소수를 구하고자 하는 범위의 모든 수를 나열한다.
2. 2는 소수이므로 2를 제외하고 2의 배수를 모두 지운다.
3. 남은 수 중 3은 소수이므로 3을 제외한 3의 배수를 모두 지운다.
4. 위의 과정을 반복하여 남는 수들이 바로 소수가 된다.

이때도 마찬가지로 \(\sqrt{n}\)까지만 확인하면 주어진 범위까지의 소수를 모두 구할 수 있다.

 

def prime_list(n):
    # n을 포함시키기 위함
    n += 1
    # 0부터 n까지 숫자가 소수라면 True, 소수가 아니라면 False 값을 갖는 배열 생성
    # [False(0), False(1), True(2), True(3), True(4), ..., True(n)]
    sieve = [False, False] + [True] * (n)

    # n의 제곱근까지 검사
    end = int(n ** 0.5) + 1
    for i in range(2, end):
    	if sieve[i] == True:			# i가 소수인 경우
            for j in range(i + i, n, i):	# i를 제외한 i의 배수들을 False 판정
                sieve[j] = False
    return [i for i in range(n) if sieve[i] == True]

 

위의 코드에서는 list를 사용하였지만 list 대신 deque를 사용하면 시간을 더 단축시킬 수 있다.