수학 : 최대공약수와 최소공배수, 소수 구하기

최대공약수 GCD

- 유클리드 호제법 O(logn)

r = a%b

gcd(a,b) = gcd(b, r)

...

r == 0 -> b 는 최대공약수

반복문 혹은 재귀로 해결 가능하다.

​

최소공배수 LCM

lcm = a*b/gcd

​

소수

1. N이 소수인지 체크하기 - 2~[루트N] 으로 나누었을 때 나누어 떨어지는게 있는지 확인 O(루트N)

2. 에라토스테네스의 체 O(nloglogn)

2~N 까지 모든 숫자를 적어놓고

가장 작은 수 ( = 소수) 의 배수들을 모두 지운다.