약수, 소인수분해, 최대공약수/최소공배수 알고리즘

약수

1. Simplest Version : $O(n)$

set<int> getFactorNumber(int n){
    set<int> v;
    for(int i = 1; i <= n; i++){
        if(n % i == 0) v.insert(i);
    }
    return cnt;
}

 제일 simple하게 brute-force로 접근하면 1~n까지 수가 n을 나누는지 보면 된다. 이 경우 O(n)이다.

 

 

2. 약수의 특성을 이용한 버전 : $O(\tfrac{n}{2})$

set<int> getFactorNumber(int n){
    set<int> v;
    for(int i = 1; i <= n/2; i++){
        if(n % i == 0){
            s.insert(i);
            s.insert(n%i);
        }
    }
    return cnt;
}

 어떤 수 n의 약수 x는, x * x = n이 아닌 이상 n/x를 약수로 가진다. 이를 이용해 i가 $\tfrac{n}{2}$까지만 설정할 수 있다.

 

 

3. 2.를 개선한, 제일 빠른 버전 : $O(n^{0.5})$

set<int> getFactorNumber(int n){
    set<int> v;
    for(int i = 1; i <= sqrt(n); i++){
        if(n % i == 0){
            s.insert(i);
            s.insert(n%i);
        }
    }
    return cnt;
}

for문을 $\sqrt{n}$ 돌리는 이유는 1부터 $\sqrt{n}$까지 n의 약수가 없다면 n은 소수이기 때문이다. 증명은 아래를 보자.

theorem) 자연수 n에 대해 n의 어떤 약수 x와 n/x에 대해 min(x, n/x) <= $\sqrt{n}$이다.

그렇기 때문에, 2번 알고리즘처럼 검사하되, i는 $\sqrt{n}$보다 작거나 같을 때까지만 검사하면 된다.

시간복잡도는 for문을 $\sqrt{n}$번 도니까 $O(\sqrt{n})$인 건 자명하다.

 

 

 

소인수분해

1. simplest version : 합성수인 경우 $O(\sqrt{n} logn)$,  소수인 경우 $O(\sqrt{n})$

vector<int> getPrimeFactorization(int n){
    vector<int> v;
    for(int i = 2; i <= sqrt(n); i++){
        while(n % i == 0){
            v.push_back(i);
            n /= i;
        }
    }
    if(n > 1) v.push_back(n);
    return v;
}

 그냥 모든 수 돌려가면서 약수를 구해과는 과정이다. 평균적으로 이게 더 간단하니 이걸 쓰면 될 것 같다.

 outer for loop를 $\sqrt{n}$까지 쓰는 이유는, 앞에서 증명한

자연수 n에 대해 n의 어떤 약수 x와 n/x에 대해 min(x, n/x) <= $\sqrt{n}$이다.

에서

2...$\sqrt{n}$까지 나눴을 때 n의 약수가 없다면 n은 소수다

를 유도할 수 있다. 증명 과정은 간단하다. "2 ... $\sqrt{n}$ 중 n의 약수가 없다면 n은 소수다."의 대우는 "n이 소수가 아니라면(합성수라면) 2 ... $\sqrt{n}$ 중 n의 약수가 존재한다" 인데, 이는 위에서 이미 보인 사실이다.

 시간복잡도는 
 - 합성수의 경우, n을 i로 나눠서 1이 될 때 까지 while을 돌리는데 i가 2일 때 O(logn)이고, i가 더 크면 값이 더 작아질 것이므로 while문의 시간복잡도는 $O(logn)$, 외부 for문이 $\sqrt{n}$번 도니 $O(\sqrt{n} logn)$
 - 소수일 경우 for문이 $\sqrt{n}$번 도니 $O(\sqrt{n})$

 

 

 

2. 조금 복잡한 버전 : $O(\sqrt{n} logn)$

vector<int> getPrimeFactorization(int n){
    vector<int> v;
    while (n % 2 == 0){
        v.push_back(2);
        n = n/2;
    }
    for(int i = 3; i <= sqrt(n); i += 2){ // outer for loop
        while(n % i == 0){                // inner while loop
            v.push_back(i);
            n /= i;
        }
    }
    if(n > 2) v.push_back(n);
    return v;
}

 시간복잡도는 위 코드와 동일하지만, outer for loop에서 i+=2므로 i의 경우의 수가 2배로 줄어든다. 그래서 위 버전보다 조금 더 빠르다.

 

 

 

최대공약수 / 최소공배수

유클리드 호제법 : $O(log(min(a, b)))$

int gcd(int a, int b){
    while(b != 0){
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int lcm(int a, int b){
    return a * b / gcd(a, b);
}

 코드는 위와 같다. 이 코드는 유클리드 호제법 -Euclidean algorithm- 이라 불리기도 한다. 지금부터 이를 증명하겠다.

 

 

이 유클리드 호제법을 확장시켜 베주의 정의($am + bn = gcd(m, n)$의 해가 되는 a, b 쌍)의 해를 찾아낼 수 있다.

최소공배수는, $lcm(a, b) = gcd(a, b) * a/(gcd(a, b)) * b/(gcd(a,b))$로 구할 수 있기 때문에,
$a * b / gcd(a, b))$로 간단하게 구할 수 있다.

 시간복잡도는 $O(log(min(a, b)))$이다. 증명과정은 아래와 같다.

 

 증명이 살짝 빠졌는데, 그러면 $a_{k}$ = $x^{n}$이라 둘 수 있다. 그러면 $log_{x}a_{k} = log n$, 즉 k번째 항을 구하는 데 log n번이 걸린다. 따라서 logn번만에 $a_{k}$가 $a_{0}$으로 온다.

​