[기초] 나머지 연산, 약수, 최대공약수, 소수

나머지 연산

어떠한 수 M 으로 나눈 나머지를 답으로 출력하라는 문제가 있다면 (자료형의 범위를 초과하기 때문에), 계산마다 항상 나누어주면 된다.

사칙연산 중에서 덧셈과 곱셈, 뺄셈은 이에 항상 성립한다. 뺄셈의 경우에서는 음수를 주의해야한다.

나누기에는 성립하지 않는다

최대공약수

유클리드 호제법 이용.

a를 b로 나눈 나머지를 r 이라고 하였을 때,

$$GCD(a, b) = GCD(b,r)$$

이다.