(참조)약수 관련

약수관련하여 총정리해본다.

 

약수관련해서는 다음과 같은 내용을 알아야 한다.

번호	항목	설명
1	어떤 수 n에 대한 약수 구하기.	- 약수는 어떤 수 n을 나누는 모든 수
2	어떤 수 n에 대한 소인수분해 하기.	- 소인수분해는, 어떤 수 n을 나눌 수 있는 소수들의 지수승의 곱으로 나타낸 것
3	어떤 수 n에 대한 약수의 개수 구하기	- 약수의 개수는, 모든 약수를 구해서 그 개수를 셀수도 있으나, 소인수분해를 한 후 그 지수승을 이용해서 구하는게 정석 - 예를들어 $12=2^2 \times 3$, 약수의 개수는 (3+1)(1+1)=8개
4	어떤 수 n에 대한 약수의 합 구하기	- 약수를 모두 구해서 합을 구하는 것보다, 소인수분해를 한 후 구하는게 정석 - n=12의 경우 약수의 합은 (1+2+4)(1+3)=28
5	어떤 수 n에 대한 약수의 곱 구하기	- n=12의 경우 약수의 곱은 $1 \times (2 \times 4) \times 3 \times (2 \times 4) = 8 \times 24 = 192$
6	최대 공약수
7	최소 공배수
8	친화수
9	완전수, 과잉수, 부족수

 

1. 어떤 수 n에 대한 약수 구하기

---

어떤 수 n에 대한 약수를 i라고 한다면 $n % i == 0$이다. 

약수를 구하는 가장 간단한 방법은, n보다 작은 정수 i에 대해 $n % i == 0$이 되는지 확인해 보는 것이다.

이때, $2..=\sqrt{n}$ 까지만 조사하면 된다. 

 

예를 들어 12의 약수를 구한다면 $\sqrt{12}=3$이다. 실제 제곱근을 floor한 값이다. 

약수는 $2..=3$ 까지만 조사해 보면 된다. 

• 12 % 2 = 0  --> {2, 6}이 약수
• 12 % 3 = 0 --> {3, 4}가 약수

여기에 1과 자기 자신이 12를 합쳐서 {1,2,6,3,4,12}가 약수가 된다.

//1-1. 약수 구하기: brute-force
#[cfg(test)]
//n에 대한 모든 약수를 구한다.
fn get_divisors(n:usize) -> Vec<usize>{   
    let mut v:Vec<usize> = Vec::new();
    v.push(1);  //1은 모둔 수의 약수

    let sqrt_n = (n as f64).sqrt() as usize; //sqrt(n)까지만 조사해도 충분
    for i in 2..=sqrt_n {
        if n % i == 0 {
            v.push(i); v.push(n/i);            
        }        
    }
    if n == sqrt_n * sqrt_n {v.pop();} //n=25의 경우 5가 2번 들어가 있음. 해서, 마지막 5를 제거
    v.push(n); //자기자신도 약수
    return v;
}

코드에서 for 루프를 벗어난 후, $n == sqrt_n * sqrt_n $ 인지 확인했다. 이는 n=25와 같은 경우는, for 루프에서 {5, 5}가 두 번 약수인 것처럼 벡터에 들어가기에, 이 중 하나를 빼기 위해서이다. 

 

2. 소인수 분해  

---

정수 n을 소수들의 지수승의 곱으로 표현하는 것을 소인수분해라 한다.

 

소인수분해를 하고 나면, 이를 통해 약수의 개수도 알 수 있고, 약수의 합과 곱도 쉽게 알 수 있다.

 

어떤 수에 대해 이 수가 어떤 소수의 곱인지를 알아내는 특별한 알고리즘은 없다. 모두 다 대입을 해보는 수밖에 없다. 

즉, 어떤 수 n에 대해, 그 보다 작은 소수들로 나눠가면서 $n % p == 0$이 되는지 확인해 가며 구할 수밖에 없다.

 

먼저, 소수가 아닌 그냥 2부터 시작되는 정수들을 이용해서 $n % i == 0$이 되는지 확인하면 소인수분해를 하는 코드를 짜 보겠다. 이처럼 소수가 아닌 그냥 2부터 나눠가면서 해도, 끝내는 소수의 곱만 남게 된다.

//2-1. 소인수 분해: 2보다 큰 일반 정수들로 나눠가면서 구한다. 
#[cfg(test)]
//n에 대해 소인수 분해
fn factorization(mut n:usize) -> std::collections::HashMap<usize,usize> {
    use std::collections::HashMap;
    let mut f_map:HashMap<usize, usize> = HashMap::new();

    let sqrt_n = (n as f64).sqrt() as usize;
    for i in 2..=sqrt_n {        
        while n % i == 0 {
            if f_map.contains_key(&i){
                f_map.insert(i, f_map[&i]+1);
            }else{
                f_map.insert(i, 1);
            }            
            n /= i;
        }        
    }
    if n != 1 {f_map.insert(n, 1);}
    return f_map;
}

 

 

작은 수 n에 대해서는 위와 같이 2보다 큰 정수들을 차례로 나눠보면서 구해도 큰 속도 문제없으나, 아주 큰 수에 대해서는 모든 정수에 대해서 검사해야 해서 속도가 느려진다. 

 

소수에 대해서만 나눠지는지 확인하면 큰 수에 대해서도 꽤 빠르게 소인수 분해할 수 있다. 

소수는 $\sqrt{n}$ 이하까지만 구하면 되고, 소수를 구하는 것은 에라토스테네스의 체를 이용해서 비교적 빨리 구할 수 있다. 

//2-2. 소인수분해: 소수구한 수 이용
#[cfg(test)]
//n에 대해 소인수 분해
fn factorization1(mut n:usize) -> std::collections::HashMap<usize,usize> {
    use std::collections::HashMap;

    //1. 소수 확보    
    let sqrt_n = (n as f64).sqrt() as usize;
    let primes = find_primes(sqrt_n);

    //2. 소인수분해
    let mut f_map:HashMap<usize, usize> = HashMap::new();
    for p in primes {        
        while n % p == 0 {
            if f_map.contains_key(&p){
                f_map.insert(p, f_map[&p]+1);
            }else{
                f_map.insert(p, 1);
            }            
            n /= p;
        }        
    }
    if n != 1 {f_map.insert(n, 1);}
    return f_map;
}

#[cfg(test)]
//find all primes <= n
fn find_primes(n:usize) -> Vec<usize> {
    //1. sieve
    let mut sieve:Vec<usize> = vec![1; n+1];
    sieve[0]=0; sieve[1]=0;
    let sqrt_n = (n as f64).sqrt() as usize;
    for i in 2..=sqrt_n {
        for j in (2*i..=n).step_by(i) {
            sieve[j] = 0;
        } 
    }
    //2. primes
    let mut primes:Vec<usize> = Vec::new();
    for i in 2..sieve.len() {
        if sieve[i] == 1 {primes.push(i);}
    }
    return primes;
}

 

3. 약수의 개수 구하기

---

약수의 개수는, 모든 약수를 구해서 그 숫자를 세면 되나, 큰 수에 대해서는 소인수분해를 한 후 그 지수를 이용해서 구하는 것이 속도가 빠르다. 소인수분해는 $\sqrt{n}$보다 작은 소수에 대해서만 조사하면 되기 때문이다. 

 

어떤 수 n에 대해 소인수분해한 것이 $n = p^a \times q^b$라면, n에 대한 약수의 개수는 $(a+1)(b+1)$이다.

즉, 소인수분해 했을 때 각 소인수에 대한 (지수+1)을 곱한 것이 약수의 개수이다. 

 

//3. 약수의 개수: 소수 이용한 소인수 분해 후 개수 구한다.
#[cfg(test)]
fn get_divisors_count(mut n:usize) -> usize {
    let sqrt_n = (n as f64).sqrt() as usize;
    let primes = find_primes(sqrt_n);

    let mut cnt = 1;
    for p in primes {
        let mut e = 1;
        while n % p == 0 {
            e += 1;
            n /= p;
        }
        if e > 1 {cnt *= e;}
        if n == 1 {break;}
    }
    if n != 1 {cnt *= 2;}
    return cnt;
}

 

4. 약수의 합 구하기

---

어떤 수 n의 모든 약수의 합은, 약수를 모두 구한 후 합을 해도 되나, 큰 수에 대해서는 소인수분해를 한 후 구하는 것이 빠르다. 

 

12를 소인수 분해하면 $12 = 2^2 \times 3$이로, 12의 약수의 합은 $(2^0+2^1+2^2)(3^0+3^1)=7 \times 4=28$

 

#[cfg(test)]
// calculate sum of all divisios of n
// n = 12, 12=2^2 x 3, sum=(1+2+4)(1+3)=28 {1,2,3,4,6,12}
// n = 10, 10=2 x 5, sum=(1+2)(1+5)=18  {1,2,5,10}
// n = 4, 4 = 2 x 2, sum = (1+2+4) = 7 {1,2,4}
fn get_divisors_sum(num:usize) -> usize{
    let mut n = num;
    let sqrt_n = (n as f64).sqrt() as usize;
    let primes = find_primes(sqrt_n);

    let mut ans = 1;
    for i in primes {
        let mut sum = 1;
        let mut ii = i;
        while n % i == 0 {  
            sum += ii;
            ii *= i;
            n /= i;
        }
        ans *= sum;
        if n == 1 {break;}
    }
    if n != 1 {ans *= 1+n; } //n=10의 경우, n=5에서 벗어남
   
    return ans;
}

 

 

 

-끝-