[정수론] 약수, 배수, 최대공약수, 최소공배수와 관련된 알고리즘
공약수와 최대공약수(GCD), 공배수와 최소공배수(LCM), 유클리드의 호제법 (Euclidean Algorithm)나눗셈 정리 (Division Algorithm)임의의 정수 $a, b\ (b \neq 0)$에 대하여 $a = bq + r$, $0 \le r 파이썬 코드에서는 간단히 구할 수 있다.q = a // br = a % b 약수와 배수 (divisor and multiple)두 정수 $a, b \ (b \neq 0)$에 대하여 $b=ac$를 만족하는 정수 $c$가 존재할 때, $b$를 $a$의 배수(multiple)라 하고 $a$를 $b$의 약수(divisor) 또는 인수(factor)라 한다. 이때 "$a$는 $b$를 나눈다" 또는 "$b$는 $a$에 의하여 나누어떨어진다" 라고 하고, ..
2024. 8. 10.
