소수 찾기 알고리즘

코테를 준비하다보니 특정 숫자가 소수(prime number)인지 아닌지 판별하는 문제가 많다.
그래서 알고리즘을 기본적으로 외우는게 편할 거 같아 정리해두려 한다.

---

일단 x가 소수인지 확인하는 간단한 방법은 2부터 x-1까지 x에 나눠보고 나눠 떨어지는게 하나라도 없으면 소수라고 판별하는 방법이다.

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

그러나 위와 같은 방법은 x가 커지면 굉장히 비효율적이다.

더 빠르고 효율적인 방법은 바로 2부터 x의 제곱근까지만 나눠서 확인하는 방법이다.
예를 들어, 소수 25의 약수는 1, 5, 25이다. 자기 자신을 제외한 약수가 존재하는지 확인하려면 어차피 대칭으로 짝을 이루기 때문에 제곱근까지만 확인하면 된다는 아이디어이다.

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