[알고리즘] 제곱근으로 소수 구하기

개념

어떤 수 n이 소수인지 아닌지를 효율적으로  판별할 수 있는 방법이다. 

 

100을 구하는 방법으로는 

• 1 * 100
• 2 * 50
• 4 * 25
• 5 * 20
• 10 * 10 
• 20 * 5
• 25 * 4
• 50 * 2
• 100 * 1

이 있다. 

 

(√100 이하의 수) * ( √100 이상의 수 )로 100을 구할 수 있는 것을 알 수 있다.

 

이 방법을 이용하면

n을 √n이하의 수로 나누고 만약 모든 수에서 나누어지지 않는다면 n은 소수, 아니면 n은 소수가 아닌 것을 알 수 있다.

 

시간복잡도는 O(sqrt(n))이다. 

 

 

구현

bool IsPrime(int n)
{
    if(n <= 1)
        return false;
    
    if(n <= 3)
        return true;
    
    for(int i = 2; i <= sqrt(n); i++)
    {
        if(n % i == 0)
            return false;
    }
    
    return true;
}