[Algorithm] 배수(Multiple)와 약수(Divisor)

배수(Multiple)와 약수(Divisor)

배수(Multiple)

• 어떤 수에다 1배, 2배, 3배, 4배, ... 한 수들을 그 수의 배수(Multiple)라고 한다.
• 예) {3, 6, 9, ...} 는 3의 배수이다.

 

예제 

1부터 100 사이의 3의 배수 출력하기

#include <iostream>
using namespace std;

int main() {
    for (int i = 1; i <= 100; i++) {
        if (i % 3 == 0) {
            cout << i << " ";
        }
    }
    return 0;
}

3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99

 

약수(Divisor)

• 어떤 수를 나누었을 때, 나누어 떨어지게 하는 자연수를 어떤 수의 약수(Divisor)라고 한다.
• 또한 모든 수는 1로 나누었을 때, 나누어 떨어지므로 1은 모든 수의 약수이다.
• 예) 1, 2, 3, 4, 6, 12로 12를 나누게 되면 12는 나누어 떨어지므로 1, 2, 3, 4, 6, 12는 12의 약수이다.

 

단순한 방법으로 약수 구하기

• 약수를 구하려는 값(@N@)을 @1@부터 @N@까지의 숫자로 나누면서, 나머지가 0인 값을 약수로 처리하는 방법이다.
• 이 방법은 $O(N)$ 의 시간 복잡도를 갖는다.

 

예제 

12의 약수 출력하기

#include <iostream>
using namespace std;

int main() {
    for (int i = 1; i <= 12; i++) {
        if (12 % i == 0) {
            cout << i << " ";
        }
    }
    return 0;
}

1 2 3 4 6 12

 

효율적으로 약수 구하기

• 약수를 구하려는 값(@N@)을 @1@부터 @$sqrt(N)$@까지의 숫자로 나누면서, 나머지가 0인 값과 몫이 0인 값들을 약수로 처리하는 방법이다.
• 이 방법은 $O(\sqrt{N})$ 의 시간 복잡도를 갖는다.

 

예

• 10의 약수를 찾는 경우를 생각해보자.

10 % 1 = 0
10 % 2 = 0
10 % 3 = 1
10 % 4 = 2
10 % 5 = 0
10 % 6 = 4
10 % 7 = 3
10 % 8 = 2
10 % 9 = 1
10 % 10 = 0

• 10이 0으로 나누어 떨어지게 하는 수는 @1@, @2@, @5@, @10@으로, 이는 10의 약수에 해당한다.
• 이 과정은 @1@부터 @10@까지의 모든 수를 이용하여 약수를 찾으므로, $O(N)$ 의 시간 복잡도를 갖는다.

---

• 100의 약수를 찾는 경우를 생각해보자.
• 우선, 100을 1부터 100의 제곱근($\sqrt{100}$)인 $10$ 까지 숫자로 나눈 나머지를 살펴보자.

100 % 1 = 0
100 % 2 = 0
100 % 3 = 1
100 % 4 = 0
100 % 5 = 0
100 % 6 = 4
100 % 7 = 2
100 % 8 = 4
100 % 9 = 1
100 % 10 = 0

• 위의 과정을 통해서 100의 약수는 일단 @1@, @2@, @4@, @5@, @10@을 갖는다는 것을 확인할 수 있다.
• 이제 100에 이미 구해진 약수들을 나누어(@/@) 보자.

100 / 1 = 100
100 / 2 = 50
100 / 4 = 25
100 / 5 = 20
100 / 10 = 10

• 이 과정을 통해 나머지 약수들(@10@, @20@, @25@, @50@, @100@)을 구할 수 있음을 확인할 수 있다.
• 단, 약수 @10@이 2번 중복되므로, 중복 처리를 해줘야 한다.
  • @약수를 구하려는 값 / 나누는 값 = 나누는 값@일 경우, 약수로 처리해주지 않는다.
• 이 방법은 시간 복잡도가 $O(\sqrt{N})$ 이므로, 10억개의 입력이 들어온다고 해도 약 3만번의 연산으로 약수를 구할 수 있다. 따라서, 코딩 테스트 문제를 풀 때 시간 초과가 발생하는 일은 없다.

 

예제

100의 약수 출력하기

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> divs;

int main() {
    for (int i = 1; i <= sqrt(100); i++) {
        if (100 % i == 0) {
            divs.push_back(i);
            if (i != 100 / i) {    // 중복 처리
                divs.push_back(100 / i);
            }
        }
    }
    
    // 오름차순 정렬
    sort(divs.begin(), divs.end());
    
    for (auto i : divs) {
        cout << i << " ";
    }
    
    return 0;
}

1 2 4 5 10 20 25 50 100