유클리드 호제법(최대공약수) GCD(A, B)=GCD(B, A% B)이다. 계속하다가 A%B가 0이 될 때 B가 원래 A, B의 최대 공약수가 된다. EX) (6,4)->(4,2)->(2,0) 6,4의 최대 공약수는 2 최소공배수는 A*B/GCD(A, B)이다. 소수 구하기 제일 좋은 방법은 에라토스테네스의 체이다. 시간 복잡도는 N개의 수에 대한 소수를 구할 때 NlglgN이다. 2에서부터 N까지 수에서 제일 작은 수로 나누어지는 수를 삭제한다. 그럼 처음에는 4, 6, 8... 이 없어진다. 다음에는 제일 작은 수인 3으로 나누어지는 수를 삭제한다. 삭제되는 것을 잘 보다 보면 2를 삭제할 때는 삭제되는 처음 수가 2*2이고 3을 삭제할 때는 삭제되는 처음 수가 3*3인 것처럼 처음 삭제되는 수는 i..