에라토스테네스의 체와 제곱근 비교 시간 차 파이썬 구현

에라토스테네스의 체와 제곱근 방식은 소수를 구하는 알고리즘 중 가장 대표적인 방식입니다.

 

대략적으로 어느 정도 차이난다는 거는 구글링으로 알긴했는데 귀찮지만 직접 구현해 보았습니다...

 

 

 

start!

 

---

⚙️ 동작 방식 

 

제곱근: N이 소수인지 판별하기 위해, N보다 작거나 같은 자연수 중 가장 큰 수인 sqrt(N)까지만 확인하는 방식입니다.

 

에라토스테네스의 체: 범위 안에서 소수를 찾는 방식으로, 2부터 시작하여 배수들을 지워나가는 방식입니다. 물론 제곱근도 사용하고 제곱근 안의 배수들을 사용해서 시간을 줄입니다.

 

 

⏱ 시간 복잡도

제곱근: O(sqrt(N))

에라토스테네스의 체: O(NloglogN)

🚀 구현

import time

def find_primes(start, end):
    # 에라토스테네스의 체 알고리즘을 사용하는 방법
    ## sieve 시작!
    start_time = time.time()
    is_prime = [True] * (end + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(end ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, end + 1, i):
                is_prime[j] = False
    primes = [i for i in range(start, end + 1) if is_prime[i]]
    end_time = time.time()
    sieve_time = end_time - start_time
    ## sieve 끝


    # 제곱근을 사용하는 방법
    # --sqrt 시작!--
    start_time = time.time()
    def is_prime_sqrt(n):
        if n <= 1:
            return False
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                return False
        return True

    primes = [i for i in range(start, end + 1) if is_prime_sqrt(i)]
    end_time = time.time()
    sqrt_time = end_time - start_time
    # --sqrt종료--
    return sieve_time, sqrt_time

 

두 개의 매개변수를 받아서, start 이상 end 이하의 소수를 찾아서,

 

에라토스테네스의 체 알고리즘과 제곱근 함수를 사용한 방법 각각에 대해서 실행시간을 측정한 후, 두 방법의 실행시간을 반환했습니다.

 

이제 이 함수를 실행시켜서, 두 방법의 실행시간을 비교해 보겠습니다.!!

대략 25배이상..

하지만 수가 작을 땐, 시간차이 많이 나지 않습니다.

 

반대로 제곱근을 이용하는 건 수가 커질 수록 시간이 더 오래 걸리니 범위 내에 큰 소수를 알고 싶을때 사용하면 됩니다.