[C] 소수 판별하기 / 에라토스테네스의 체 / 소인수 분해

1. 소수 판별하기

 

소수는 양의 약수가 1과 자기 자신 두 개 뿐인 자연수를 의미한다

정수를 입력하였을 때 이를 판별할 수 있는 가장 단순한 알고리즘을 알아보도록 하자

 

1, 2 예외 처리 후, 3 ~ n-1의 모든 수를 순회하며 n의 약수가 있는지 확인하는 방법이 있다

 

최적화 1) √n * √n = n 이므로, n-1까지 순회하는 대신, √n까지만 순회한다

최적화 2) 2를 예외 처리한다면 그 외 모든 짝수는 합성수이므로 배제한다

 

두 가지의 최적화를 거친 후, 코드는 다음과 같다

 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> //bool, true, false
#include <math.h> //sqrt()

_Bool isPrime(int n)
{
    if (n <= 1) return false; //1 제외
    if (n == 2) return true; //2 제외
    if (n % 2 == 0) return false; //짝수 배제

    int sqrtn = (int)sqrt(n);
    for(int div=3 ; div <= sqrtn ; div++) //√n까지 순회
    {
        if(n % div == 0) return false;
    }
    return true;
}

 

---

 

2. 에라토스테네스의 체가 무엇인가 ?

 

에라토스테네스의 체는 수학에서 소수를 찾는 방법 중 하나이다

 

 

위와 같이 120까지의 소수를 구하려고 한다면

2, 3, 5, 7, 11 (2 ~ 11 사이의 소수 ; 11*11 > 120 이므로 그 이상의 소수는 필요 없음)

의 배수들을 하나씩 지워주는 방법이다

 

최적화 1) 이 역시 소수 판별 때와 같이 √n까지만 찾는다

최적화 2) 배수들을 지울 때 2*i에서 시작하는 것이 아닌, i*i에서 시작한다. (i-1)*i는 전에 이미 지워졌기 때문이다

 

코드는 다음과 같다

 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> //true, false
#include <math.h> //sqrt()

_Bool nums[121];

void eratosthenes()
{
    for(int i=0 ; i<=121 ; i++) nums[i] = true; //true로 초기화 후, 합성수 제외
    nums[0] = nums[1] = false; //1 제외

    int sqrtn = (int)sqrt(120); //√120 > 11 이므로 11까지 순회 (11*11 < 120)
    for(int i=2 ; i <= sqrtn ; i++)
    {
        if(nums[i])
        {
            for(int j=i*i ; j <= 120 ; j += i) nums[j] = false;
        }
    }
}

 

---

 

3. 소인수 분해

 

소인수 분해는 한 합성수를 소수들의 곱으로 표현하는 방법을 말한다

 

가장 간단한 방법은

2부터 시작해 n의 소인수가 될 수 있는 수들을 순회하면서, n의 약수를 찾을 때마다 나누는 방법이 있다

n이 소수인 경우 √n번 반복문을 돌기 때문에 시간 복잡도는 O(√n)이 된다

이 범위의 소수들을 미리 찾아둔다면, 훨씬 빨라지는 최적화 방법이 될 것이다

 

코드는 다음과 같다

 

~

    int n = 120; //120 소인수 분해
    int ret[10]; //소인수 저장 배열
    int idx = 0; //소인수 인덱스 값
    
    for(int div = 2 ; div <= 11 ; div++) //2~11 숫자 선회
    {
        while(n % div == 0) //약수인 경우
        {
            n /= div;
            ret[idx++] = div;
        }
    }
    if(n > 1) ret[idx++] = n; //소수인 경우
    
~

 

이를 에라토스테네스의 체를 이용하여 더 빠른 소인수 분해를 구현해보자

 

체를 실행할 때

각 숫자의 소수 판별을 기록하는 것뿐 아니라,

각 숫자의 가장 작은 소인수를 같이 기록해 둔다면 합성수를 더 쉽게 계산할 수 있다

 

이를테면, 에라토스테네스의 체 코드에서,

nums[] 배열에 단순히 true/false를 기록하는 것이 아니라

가장 작은 소인수를 기록하는 것이다 (소수일 경우 nums[i] == i)

 

코드는 다음과 같다

 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int nums[121];

void eratosthenes2()
{
    for(int i=2 ; i<=120 ; i++) nums[i] = i;
    nums[0] = nums[1] = -1;

    int sqrtn = (int)sqrt(120);
    for(int i=2 ; i <= sqrtn ; i++)
    {
        if(nums[i] == i)
        {
            for(int j=i*i ; j <= 120 ; j += i)
                if(nums[j] == j)
                    nums[j] = i;
        }
    }
}

int main()
{
    eratosthenes2();

    int n = 120;
    int ret[10];
    int idx = 0;

    //바뀐 부분
    while(n > 1)
    {
        ret[idx++] = nums[n];
        n /= nums[n];
    }

    return 0;
}