[ 알고리즘 ]/Mathematics

[T-academy] 최대공약수, 최소공배수, 소인수분해, 소수판별법

[ 최대공약수, 최소공배수 ] 최대공약수 : a, b 중 더 작은 수까지만 체크해도 됨. 거꾸로 체크해 나가기 최소공배수 유클리드 호제법 GCD(a, b) = GCD(b, a%b) # 최대공약수(gcd) sol1 def gcd(a, b): ret = 0 for i in range(min(a, b)): # 1부터 체크 if a % i == 0 and b % i == 0: ret = i return ret # 최대공약수(gcd) sol2 => fast(가장 큰 수부터 체크해서 조건 만족시 ret) def gcd(a, b): for i in range(min(a, b), 0, -1): # min(a, b)부터 거꾸로 체크 if a % i == 0 and b % i == 0: return i # 최대공약수(gc..