유클리드 호제법

약수 구하기

• N의 약수의 개수 구하는 방법
  - 1부터 N 이하까지 나누어보깅~ O(N)
  - 1부터 √N 이하까지 나누어보고 *2~ O(√N)
  

유클리드 호제법 (최대 공약수 구하기)

• a , b, a%b = r 일때
• a b의 최대 공약수는 b r의 최대 공약수와 동일

a%b = r 이고
b%r = r' ... 이런식으로 쭉 간ㄷ ㅏ
마참내 어딘가에서
r'%r'' = 0 으로 나누어 떨어진다면
a와 b의 최대 공약수 또한 r''

최대공약수 GCM, 최소공배수 LCM

어떤 두 수 A, B
A = G Q
B = G W
G = 두 수의 최대공약수라면, 최소 공배수는 GQW
두 수의 곱 AB는 곧,
GCM LCM인 GGQ*W 과 같다

code 작성

cpp는 라이브러리 제공함
엌ㅋ

#include <numeric>
#include <iostream>
using namespace std
int main(){
	cout << gcd(18,24)<< endl;
    return 0;
}