[math] 약수(divisor)

1. 약수란? 

어떤 수를 나누어 떨어지게 할 수 있는 수 

#include <bits/stdc++.h>
using namespace std;

vector<int> find_divisor(int n) {
	vector<int> divisor; 
	for (int i = 1; i * i <= n; i++) {
		if (n % i == 0) divisor.push_back(i);
	}
	for (int i = (int)divisor.size() - 1; i >= 0; i--) {
		if (divisor[i] * divisor[i] == n) continue; 
		divisor.push_back(n / divisor[i]);
	}
	return divisor;
}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int x; 
	cin >> x; 
	vector<int> ans = find_divisor(x); 
	for (auto d : ans) cout << d << ' ';
}

어떤 합성수 N이 존재할 때, root(N) 이하로 약수를 탐색하면, 모든 약수를 구할 수 있다. 

또한, (int)로 형변환을 한 이유는 vector는 size를 반환할 때, unsigned_int type이므로, 오류가 날 수 있다. 따라서, (int)로 형변환 해주는 것이 좋다고한다. 

출처 : https://www.youtube.com/watch?v=2RCJApSVxRI&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=19

 

2. 최대공약수(GCD) 

유클리드 호제법을 이용한다. 유클리드 호제법이란 두 자연수의 최대공약수를 구할 때 사용하는 알고리즘이다. 

int a , int b ; 크기순서는 상관없다. 

a = 20, b = 12; 

gcd(20,12) --> gcd(12,8) --> gcd(8,4) --> gcd(4,0) == 4 ; 

이런식으로 구하면 된다. 

int gcd(int a, int b) {
	if (b == 0) return a; 
	return gcd(b, a % b);
}

 

3. 최소공배수(LCM) 

int a, int b; 

a * b = gcd(a,b) * lcm(a,b) 

lcm(a,b) = a / gcd(a,b) * b; 

여기서 (a * b) / gcd(a,b)로 하지않는 이유는, int overflow가 발생할 수 있기때문이다. 

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

출처 : https://www.youtube.com/watch?v=2RCJApSVxRI&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=19