[소수 판별] - 소수 판별 알고리즘의 성능

소수 판별 알고리즘 관련해서 정리를 하려고합니다. 

 

 

기본적인 소수 판별 알고리즘 

 

---

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

 

 

에라토스테네스의 체 소수 판별 알고리즘

---

 

 

def get_prime_nums(n):
    prime = [True] * n
    prime[0], prime[1] = False, False
    for i in range(2, n+1):
        if prime[i] == True:
            j = 2
            while i * j <= n:
                prime[i * j] = False
                j += 1
    return prime

 

에라토스테네스의체를 루트(제곱근)를 이용한  소수 판별 알고리즘

---

import math

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

 

 

테스트 결과는 아래와 같았다 

 

소수 펀별 알고리즘 관련해서 에라토스테네스의 체는 성능상 좋치 못한 결과를 나타났고 제곱근을 이용한 방법이 가장 좋은 성능이였다. 에라토스테네스의 체를 자주이용하여 문제를 풀곤 했었는데 넓은 범위에 소수에는 좋지 못한 성능을 나타내었다. 소수 판별에 대한 알고리즘을 사용할때는 성능에 대한걸 한번더 생각하면서 적용을 해야겠다는 생각이 들었다 

 

제곱근 :  넒은 범위에서의 많지않는 소수가 필요할때 

에라토스테네스의체 : 좁은 범위에서의 많은 소수가 필요할때 

 

사용하면 적합할것 같다 

 

왜 루트 까지 하면 소수를 판별을 할수있는지 확인을 해봐야 겠다 

 

 

 

너무나 감사한 글을 링크를 걸어 두었습니다. 

https://yeoooo.github.io/algorithm/prime_performance/