반응형 유클리드 호제법2 [C++] 유클리드 호제법을 사용해 최대공약수 구하기 유클리드 호제법 유클리드 호제법이란 2개의 자연수를 이용해 최대공약수를 구하는 알고리즘이다. 유클리드 호제법을 사용해 최대공약수를 구하는 방법 두 자연수를 각각 a와 b라고 하고 a >= b 일 때 a % b = c 계산을 한다. c가 0이 아니라면 b % c 계산을 진행한다. 나머지 값이 0이 될 때까지 반복한다. 나머지 값이 0이 되었을 때 나누는 수의 값이 두 자연수의 최대공약수이다. 예시) 78696와 19332의 최대공약수 구하기 / 최대공약수는 36이다. 78696 ＝ 19332×4 ＋ 1368 19332 ＝ 1368×14 ＋ 180 1368 ＝ 180×7 ＋ 108 180 ＝ 108×1 ＋ 72 108 ＝ 72×1 ＋ 36 72 ＝ 36×2 ＋ 0 출처) 위키백과 최대공약수 구하기 유클리드 .. 2024. 1. 19. [백준] [C++] 2609번 최대공약수와 최소공배수 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 코드 #include using namespace std; int divisor (int x, int y) {// 최대공약수 int z = x % y; while (z != 0) { x = y; y = z; z = x % y; } return y; } int multiple(int x, int y) {// 최소공배수 return (x * y) / divisor(x, y); } int main() { int a, b, div, mul;// div 최대공약수 mul .. 2022. 11. 22. 이전 1 다음 반응형
