소수 판별법

핵심

소수는 1과 자기자신으로 나누어 떨어지는 수

소수를 판별하는 가장 간단한 방법은

1과 자기자신을 제외한 2 ~ n-1 까지 수로 나누어서 떨어지는지 확인하는 것 이다.

이것은 O(n)의 시간 복잡도를 갖으며 이 방법을 개선한 방법으로

1과 n을 제외한 n의 약수가 존재할 때 가장 작은 약수 a는 a <= \sqrt n 이라는 명제를 가지고

O(logN)의 시간 복잡도를 갖을 수 있도록 한다.

void Funtion(int n)
{
    if (n <= 2) return false;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0) return false;
    }
    return true;
}