C++は2つの数の最大公約数を求めます

構想1:a,bの2つの数を与えて、小さい数をcに与えて、c=b(a>bを設定してもいい)にさせて、aとbをcに対して余剰演算をして、cから順番に1を減らして下へ遍歴して、両者の余剰がすべて0になるまでcを返して、さもなくば循環遍歴を続けます.
コードは次のとおりです.

#include

int gcd(int a,int b)
{	int c;
	c=(a>b)?b:a;
	while(a%c!=0||b%c!=0)
	{	c--;
	}
	return c;
}
int main()
{	int a,b,max_div;
	cout<>a>>b;
	max_div=gcd(a,b);
	cout<

構想二:転がり相除去法
a>bを仮定すると、aがbによって除去されない場合、bはaに割り当てられ、残りはbに割り当てられ、aがbによって除去されるまでa%bが繰り返し実行される.このときbの値を返すと最大公約数となる.
コードは次のとおりです.

#include


int gcd2(int a,int b)
{	int c;
	if(a>a>>b;
	max_div=gcd2(a,b);
	cout<

明らかに、方法2は方法1よりも効率的であり、使用方法2を優先的に推奨する.
参考文献:http://blog.csdn.net/a1414345/article/details/51770430