[정수론] 효율적으로 모든 약수를 구하기 (C++)

1. 일반적으로 떠올릴 수 있는 약수 구하는 방법

vector<int> function(int N){
    vector<int> v; // N의 약수

    for(int i(1);i<=N;i++){
        if(N%i==0){
            v.push_back(i);
        }
    }
    
    return v;
}

N의 양의 약수를 구하라고? 룰루랄라 1부터 N까지 나누어 떨어지면 그게 약수지!

하고 위처럼 코드를 짜면 10^12 같은 큰 수의 약수를 구할 때 매우 비효율적이다.

 

 

2. 효율적인 방법으로 약수 구하는 알고리즘

#include<math.h>

vector<int> function(int N){
    vector<int> v; // N의 약수

    for(int i(1);i<=sqrt(N);i++){
        if(N%i==0){
            v.push_back(i);
            if(i==N/i) v.push_back(N/i); // 100=10*10 처럼 약수가 중복되는 경우 제외
        }
    }

    return v;
}

어떤 수 N의 약수 집합을 살펴 보면 [1, a, b, c, ... √N, ...N/c, N/b, N/a, N] 으로 구성 되어 있음을 알 수 있다. (√N이 정수가 아닐 수도 있음)

이 말은 즉슨 N의 제곱근까지만 약수를 구하면 이후의 약수도 구할 수 있다는 의미이다. 시간복잡도 O(√N)로 획기적으로 시간을 단축할 수 있다!

 

 

100을 예시로 들면

1. √100 = 10까지만 약수를 구해 [1, 2, 4, 5, 10] 약수 집합을 얻는다.
2. 구한 약수로 100을 나눠 또 다른 약수를 구한다.
   100 / 1 = 100
   100 / 2 = 50
   100 / 4 = 25
   100 / 5 = 20
   100 / 10 = 10
3. 최종적인 100의 약수 집합은 다음과 같다. [1, 2, 4, 5, 10, 20, 25, 50, 100] 

 

---

관련 문제

SWEA 16800번 구구단 걷기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AYaf9W8afyMDFAQ9&categoryId=AYaf9W8afyMDFAQ9&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy