[Algorithm] 정수론

소수

소수판별

 

어떤 자연수 N을 입력으로 받았을 때, 그 자연수가 소수인지 아닌지 판단하는 알고리즘을 작성해보자.

어떤 자연수 N이 소수라고 한다면, 그 수는 1과 자기자신 외의 약수를 가지지 않는다.

그러므로 가장 간단하게 알고리즘을 작성한다면 2부터 N-1까지의 모든 자연수로 나누어 보고, 한번이라도 나누어진다면, 소수가 아니고, 단 한번도 나누어지지 않았다면 소수라고 할 수 있을 것이다.

하지만, 합성수의 대한 개념을 이용하면, 이 알고리즘을 조금 더 최적화시킬 수 있다.

합성수란, 1과 자기자신 외의 다른 약수를 갖고있는 수를 의미한다.

예를 들어 6은 2*3으로 표현될 수 있으므로 합성수이다.

소수와 완전 반대되는 개념을 갖으므로, 어떤 수가 합성수라면, 소수가 아니다.

어떤 자연수 N이 입력으로 들어왔을 때, 이 수가 합성수라고 가정해보자.

그렇다면 N = a * b의 형태로 표현될 수 있을 것이다. (a <= b)

이렇게 표현된 상태에서 보면 굳이 2부터 N-1까지의 수로 나누어볼 필요 없이, 2부터 a까지의 수로만 나누어봐도 이 수가 합성수인지 충분히 판단이 가능할 것이다. 그렇다면 a를 포함할 수 있는 경계범위는 어떻게 알아낼 수 있을까?

이는 제곱수에 대해 분석해보면 알 수 있다.

합성수 중에는 제곱수인 합성수도 있고, 제곱수가 아닌 합성수도 존재한다.

제곱수인 합성수 36을 a * b (a <= b) 형태로 표현하며 생각해보자.

36 = 2 * 18

36 = 3 * 12

36 = 4 * 9

36 = 6 * 6

제곱수 N을 곱의 형태로 표현해보면 확인할 수 있듯이, 어떤 합성수가 두 약수가 완전히 같아지는 순간이 이 약수의 최대경계가 되고, 제곱수일때 이런 형태로 나타난다. 그러므로 sqrt(N) 까지의 수로 나누어보면 소수인지 아닌지 판단이 가능할 것이다.

그리고 여기서 추가로 더 최적화를 한다면, 2인 경우 미리 소수로 예외처리를 해버리고 시작한다면, 모든 2를 제외한 짝수는 소수가 아님을 알 수 있다. 그리고 2의 배수에 대한 예외처리가 끝났다면, 이후 소수판별을 진행할 때, 3부터 sqrt(N)까지의 홀수만 검사하도록 추가 최적화가 가능할 것이다.

 

static bool IsPrime(int n)
    {
        if (n <= 1)
            return false;

        // 2는 예외
        if (n == 2)
            return true;

        // 모든 짝수는 2의 배수니까 소수 x
        if (n % 2 == 0)
            return false;

        // 3 5 7 9 ...
        int sqrtn = (int)(sqrt(n));
        for (int i = 3; i <= sqrtn; i += 2)
        {
            if (n % i == 0)
            {
                return false;
            }
        }
        return true;
    }

 

Time Complexity	O(N^(0.5))
Input	소수 판별 대상 정수
Output	소수 판별 (true, false)

 

 

 

에라토스테네스의 체

 

어떤 특정 자연수 N이 소수인지 판단해야 하는 상황도 있겠지만, 1부터 N까지의 모든 소수를 구하는 알고리즘도 있을 것이다. 에라토스테네스의 체 알고리즘을 이용하면 가능하다.

이 알고리즘의 기본 개념은 다음과 같다.

먼저 2부터 n까지의 모든 수를 나열한다.

2 3 4 5 6 7 8 9 10 11 ... n

이 수열의 처음 위치부터 시작해서 지워지지 않은 수들을 순회하며 그 수의 배수들을 지우기를 반복한다.

가장 먼저 지워지지 않은 2부터 시작한다.

2를 제외한 2의 모든 배수를 지운다.

2 3 5 7 9 11 ... n

다음으로 지워지지 않은 수는 3이다.

3을 제외한 3의 모든 배수를 지운다.

2 3 5 7 11 ... n

이 과정을 반복하면 체에는 모든 합성수가 제거되어 소수만 남게 된다.

 

이 알고리즘에도 최적화가 가능하다.

어떤 X를 제외한 X의 배수를 지울 때,

X의 범위는 sqrt(X)까지만 해도 충분하다. 이는 소수판별 알고리즘에서의 내용과 동일하다.

또한 지울 때 for loop의 범위는 X * X에서 시작해도 충분하다.

왜냐하면 2 * X는 2의 배수를 지울 때 지워졌을 것이고,

3 * X는 3의 배수를 지울 때 지워졌을 것이고,

(X - 1) * X는 (X - 1)의 배수를 지울 때 지워졌을 것이기 때문이다.

 

class Eratosthenes
    {
    public:
        Eratosthenes(size_t n) : n(n) {}

        void Make()
        {
            primes.resize(n + 1, true);
            primes[0] = primes[1] = false;

            int sqrtn = (int)(sqrt(n));
            for (int i = 2; i <= sqrtn; ++i)
            {
                if (!primes[i]) continue;

                for (int j = i * i; j <= n; j += i)
                {
                    primes[j] = false;
                }
            }
        }

        // O(1)
        bool IsPrime(int n) const
        {
            return primes[n];
        }

        void Print() const
        {
            for (int i = 2; i <= n; ++i)
            {
                if (primes[i])
                {
                    std::cout << i << " ";
                }
            }
        }

    private:
        size_t n;
        std::vector<bool> primes;
    };

 

Time Complexity	O(N)
Space Complexity	O(N)
Input	N
Output	N까지의 모든 소수