소수(Prime Number) 판별 및 개수 세기 - 에라토스테네스의 체(Sieve of Eratosthenes) - Python 예제

소수(Prime Number)란?

소수는 자기 자신과 1로만 나누어 떨어지는 자연수이다.

2, 3, 5, 7, 11, 13, 17 , , , 

---

소수 판별법 1 - O(N) 방식

만약 한 숫자에 대해서 소수인지 아닌지를 판별하기 위한 가장 기본적인(느린) 방법으론 2 ~ 해당 숫자인 숫자들의 나머지 연산 결과가 0인지 아닌지를 조건문을 통해 판별하면 된다.

이런 방식을 사용할 경우, 시간 복잡도는 O(N)을 갖게된다.

7에 대해서 소수 판별을 적용하면
7 % 2 = 1, 7 % 3 = 1, 7 % 4 = 3, 7 % 5 = 2, 7 % 6 = 1
따라서, 7은 1과 7을 통해서만 나누어 떨어지므로 소수이다.

이를 Python 예시로 확인하면 다음과 같다.

def isPrime_BigON(N):
    isPrimeNum=True
    for i in range(2, N):
        if N % i == 0:
            isPrimeNum=False
            break
    print("{}은 소수입니다.".format(N) if isPrimeNum else "{}은 소수가 아닙니다.".format(N))

---

소수 판별법 2 - O(N/2) 방식

첫번째 판별법 방식으로 2 ~ 특정 숫자 사이의 나머지 연산은 "특정 숫자 -2" 만큼 발생한다.

이 중에서 하나의 방법만 추가한다면 연산의 횟수를 2배나 줄이는 것이 가능하다.

 

이는 아래의 예시를 통해 설명해보겠다.

어떤 수가 나누어 떨어지는 가장 작은 자연수는 1을 제외하면, 2이다.
만약, 특정 숫자에 2를 나눈 수보다 큰 숫자들은 본래 숫자와 나누어 떨어질 수 있을까?

위에서 사용했던 7의 소수 판별 연산을 다시 살펴보면,
7 % 2 = 1, 7 % 3 = 1, 7 % 4 = 3, 7 % 5 = 2, 7 % 6 = 1
이 밑줄 친 부분은 소수를 판별하기에 필요한 연산이 아니다.

따라서, 7 % 2 = 1, 7 % 3 = 1의 연산을 통해서만으로도 7이 소수인지 아닌지를 판단할 수 있다.

따라서, 첫번째 소수 판별법에 간단한 한 부분을 추가해줌으로써, 소수 판별의 목적은 달성하면서 시간복잡도는 O(N/2)를 갖게 된다.

 

이 부분을 Python에 추가하면 아래와 같다.

def isPrime_BigONdiv2(N):
    isPrimeNum=True
    for i in range(2, int(N/2)+1):
        if N % i == 0:         
            isPrimeNum=False
            break
    print("{}은 소수입니다.".format(N) if isPrimeNum else "{}은 소수가 아닙니다.".format(N))

---

소수 판별법 3 - O(N**0.5) 방식

이는 두번째 방식을 도출한 것과 비슷한 관점이다.

이는 2 ~ 해당 숫자의 제곱근까지 나머지 연산을 수행하는 방식이다.

 

아래의 예시를 통해 이를 확인해보자

23이라는 숫자에 대해서 소수 판별을 진행할 경우
첫번째 방식으론 2 ~ 22 까지의 숫자의 연산이 필요하고,
두번째 방식으론 2 ~ 11 까지의 연산이 필요하다.

만약, 어떤 수가 소수가 아니라면, 그 수의 약수들의 관계를 살펴보며 이 방식을 확인해보자.
숫자 100의 약수들 중 이런 관계를 생각해볼 수 있다.
100 = 2 * 50 = 5 * 20 = 10 * 10

240에 대해서도 같은 방식을 적용하면,
240 = 2 * 120 = 4 * 60 = 6 * 40 = 10 * 24 
이러한 관계를 찾을 수 있다.

어떤 숫자를 숫자 2개의 곱으로 표현하고, 작은 수를 항상 왼쪽에 위치시켜 표현한다고 가정하면,
위의 예시처럼 좌항에 위치한 숫자들은 자신의 제곱근을 넘을 수 없다.

즉, 이를 적용하여 특정 숫자의 제곱근까지만 수행해도 그 수가 소수인지 아닌지를 판별할 수 있다.

수학적인 증명은 아니지만,

제곱근을 통한 소수 판별 방식을 사용한다면 시간 복잡도를 O(N**0.5) 까지 줄일 수 있다.

 

아래는 이를 적용한 Python 예시이다.

def isPrime_BigOSqrtN(N):
    isPrimeNum=True
    for i in range(2, int(N **0.5)+1):
        if N % i == 0:
            isPrimeNum=False
            break
    print("{}은 소수입니다.".format(N) if isPrimeNum else "{}은 소수가 아닙니다.".format(N))

---

에라토스테네스의 체 방식

사실 하나의 숫자에 대해 소수인지 아닌지를 판별만 하기 위해선 위의 시간복잡도로도 충분하다.

 

하지만, 특정 범위의 모든 소수의 개수를 구하거나, 이들을 리스트로 반환받아야 할 때가 오는 경우에는 결국 N만큼이 곱해진 시간 복잡도를 가질 것이다. 추가적인 트릭으로 연산을 줄일 순 있지만

 

만약 시간복잡도 제약이 존재하는 상황이라면, 수가 커질수록 급격하게 높아지는 O(N ** 1.5) 시간복잡도 때문에 연산 속도가 좋지 않을 수 있다. 

 

이러한 상황에 가장 적절하고, 가장 널리 알려진 소수 판별 알고리즘은 에라토스테네스의 체이다. 이 알고리즘의 시간 복잡도는 O(N * log log N) 이다.

 

이를 단순한 소수 판별에서 사용하면 오히려 시간 복잡도가 커지지만, 이 알고리즘의 진가는 앞서 말했듯이 범위 내의 모든 소수를 찾을 때 있다. 

 

에라토스테네스의 체의 원리는 아래와 같다.

2의 배수들은 당연히 소수가 아닐 것이고, 3의 배수 또한 당연히 소수가 아니다.
이런 식으로 지정한 범위 내의 배수를 하나씩 지워가는 방식으로 소수를 남겨 나가는 방식이다. 소수를 체를 통하여 남기는 느낌!.
 자세한 방식은 아래와 같다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 배열초 초기화한다.
2. 2부터 자기 자신을 제외한 2의 배수를 모두 지운다.
3. 3 또한 자기 자신을 제외한 배수를 모두 지운다. 
4. 4는 2의 배수를 지우는 과정에서 넘어갔으므로 5를 제외한 5의 배수를 모두 지운다.
5. 최대 범위까지 이러한 과정을 반복한다.

이러한 과정을 거쳐 배열에 남은 숫자들이 해당 범위 내의 소수들이다. 이 방식을 사용하면, 모든 수를 2부터 나머지 연산을 해야하는 과정을 줄여 전체적인 시간 복잡도를 굉장히 줄일 수 있다.

 

마지막으로 아래는 Python으로 에라토스테네스의 체를 구현한 예시이다.

def sieveOfEratosthenes(N):
    prime_list=set(range(2, N+1)) # 2부터 N을 갖는 집합 자료형 선언
    for i in range(2, N+1): # 2부터 N까지 반복
        if i in prime_list: 
            prime_list -= set(range(2*i, N+1, i)) # 차집합 연산을 통해 자신을 제외한 소수의 배수 제거
    return prime_list

파이썬 특유의 간결함과 기본 자료형의 강력함 때문에 이정도로 구현이 완성되었다.

---

 

번외. 시간 더 줄여보기

에라토스테네스의 체의 코드를 작성해보니, 반복문을 2부터 N+1까지 수행할 필요가 없다고 생각되었다.

어차피 작은 소수의 배수들은 걸러진 상태일테니 이 반복문 횟수 자체를 줄이면 시간 소요가 더 줄어들 것이라고 생각들었고, 이를 위해 소수 판별법 3의 개념을 추가적으로 도입해보았다.

기본 에라토스테네스의 체와 수정한 에라토스테네스의 결과 비교

간단한 부분만 수정한 후, 극단적인 차이를 보기 위해 2부터 천만 사이의 소수의 개수를 출력해보았다.

 

두 결과 확인과 소요 시간 확인!

혹시 결과가 틀려질까해서 결과 값을 확인해보았고, 이 부분은 문제가 없었다.

시간은 대략 0.8초가 줄어들었고, 작업 시간이 약 30% 단축된 것을 알 수 있다!