소수 판별

소수 판별을 조금 더 빠르게 할 순 없을까?

 

 

이번 글은 O(√n)이 걸리는 소수 판별 알고리즘에 대해 알아보겠습니다.

 

소수 판별

기존 소수 판별 알고리즘은 어떠한 숫자에 전부 2부터 n까지 나누는 경우 나눠떨어지면 소수가 아니라고 판별하게 됩니다.

이 알고리즘은 시간복잡도가 O(n)이 걸리게 됩니다.

 

조금 더 효율적으로 소수를 판별할 수는 없을까요?

 

소수 판별을 O(√n)의 시간복잡도로 검사하는 코드는 다음과 같습니다.

private boolean isPrime(int n) {
    if (n < 2) return false;
    
    for (int i = 2; i * i <= n; i++) {  // √n까지만 확인
        if (n % i == 0) return false;
    }
    
    return true;
}

 

코드에서 i는 2부터 √n까지의 범위로 나누는 경우 나눠떨어지면 소수가 아니라고 판별합니다.

 

왜  √n 까지의 범위가 기준이 될까요?

 

하나의 예시를 통해 알아보겠습니다.

36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36입니다.

 

약수는 항상 짝궁이 존재합니다. 약수를 짝짓는 경우 아래와 같습니다.

• 1 x 36 (1과 36이 짝)
• 2 x 18 (2와 18이 짝)
• 3 x 12 (3과 12가 짝)
• 4 x 9 (4와 9가 짝)
• 6 x 6 (6과 6이 만나는 지점이 바로 √36 = 6)

즉, 약수는 √n까지만 검사하면, 나머지는 자연스럽게 구해집니다. 

2가 약수면 18도 약수이고, 3이 약수면 12도 약수이고, 6이 약수면 그 다음부터는 이미 검사한 숫자들이 약수 관계로 등장하게 됩니다.

 

정리

• 약수는 짝궁이 있기 때문에, √n까지만 찾으면, 나머지는 자동으로 알 수 있습니다. 따라서, 그래서 √n까지만 돌리는 게 훨씬 빠르고 효율적입니다.