10042 求最大公约数

题目描述

求两个数 和 的最大公约数。

输入格式

输入二个数，即 和 的值

输出格式

输出最大公约数。

样例

输入 #1 

8 6
输出 #1 

gcd=2
数据范围与提示

欧几里得定理：

时，

时，

分类标签

[最大公约数]

C++题解代码 

#include <bits/stdc++.h>
using namespace std;

int a;
int b;
int c;


// The main procedure
int main() {
  cin>>a;
  cin>>b;
  while (b > 0) {
    c = (a%b);
    a = b;
    b = c;
  }
  cout<<"gcd=";
  cout<<a;
  return 0;
}

Blockly题解代码图片