[Algorithm C#] 소수 판별 최적화 알고리즘 (제곱근, 에라토스테네스의 체)

1. 소수란? 

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

 

- 시간복잡도 : O(log(√N)

        public static bool IsPrime(int num)
        {
            if (num < 2)
                return false;

            for (int i = 2; i < num; i++)
                if (num % i == 0)
                    return false;

            return true;
        }

2. 제곱근 활용

num = x * y 라고 했을 때 1 <= x, y <= num 이 성립한다고 가정

- x, y가 자연수라면 x, y는 num의 약수

- x, y는 서로 반비례, 대칭 관계에 있음 ( x가 커질수록 y는 작아지고 서로의 값이 바뀌여도 성립함 )

- x, y에 num의 제곱근을 넣는다면 좌우 대칭이 되므로 이후는 대칭식이 될 것

즉, 제곱근(sqrt) 범위까지만 나누어 체크하면 소수인지 판단 가능

 

- 시간복잡도 : O(sqrt(n))

        public static bool IsPrime(int num)
        {
            if (num < 2)
                return false;

            for (int i = 2; i <= Math.Sqrt(num); i++)
                if (num % i == 0)
                    return false;

            return true;
        }

3. 에라토스테네스의 체

- 이미지 출처 및 설명 : 위키백과

 

 

- 시간복잡도 : O(nlog(logn))

        public static bool IsPrime(int num)
        {
            if (num < 2)
                return false;

            bool[] primeArray = new bool[num + 1];

            for(int i = 0; i < primeArray.Length; i++)
                primeArray[i] = true;

            for (int i = 2; i * i <= num; i++)
                if (primeArray[i])
                    for (int j = i * i; j <= num; j += i)
                        primeArray[j] = false;

            return primeArray[num];
        }