判断是否是最简分数（既约分数）(辗转相除法）（暴力枚举）

判断一个分数是否为既约分数的算法（既约分数是指 分数的分子和分母的最大公约数是1 ，也称为最简分数）
最简分数，是分子、分母只有公因数1的分数，或者说分子和分母互质的分数，又称既约分数 

以下为2段代码，第一段是我一开始自己写的，第二段是网上看到的运用的数学家欧里几得的辗转相除法，第二段代码建议读者背诵。它设计的很灵活，第一段代码简明易懂，但在计数较大数值时花费时间较长，第二段代码可以快速计算和判断。

（暴力枚举法）

#include
//判断一个分数是否为既约分数的算法（既约分数是指 分数的分子和分母的最大公约数是1 ，也称为最简分数）
//最简分数，是分子、分母只有公因数1的分数，或者说分子和分母互质的分数，又称既约分数 

int gcd(int a,int b)
{
	int i,flat=0,n;
	(a>b)?(n=b):(n=a);
	for(i=2;i<=n;i++)
	{
		if(a%i==0&&b%i==0)
	{	flat=1; break;}
	}
	return flat;}
int main()
{//  a/b  a为分子，b为分母； 

    int a,b;
  scanf("%d%d",&a,&b);
   if(gcd(a,b)==0)
   printf("yesn");
   else printf("non") ;
 } 

 (辗转相除法）

#include
//判断一个分数是否为既约分数（既约分数是指 分数的分子和分母的最大公约数是1 ，也称为最简分数）
//最简分数，是分子、分母只有公因数1的分数，或者说分子和分母互质的分数，又称既约分数 

//在数学中，辗转相除法，又称欧几里得算法（英语：Euclidean algorithm）
//是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中
//而在中国则可以追溯至东汉出现的《九章算术》


//核心
//两个整数的最大公约数是能够同时整除它们的最大的正整数。
//辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。
//例如，252和105的最大公约数是21
//252-105=147 147是两个数的差，147和105的最大公约数是21
int gcd(int a,int b)
{
	if(a%b==0)
		return b;
	else
		return gcd(b,a%b);
}
int main()
{//  a/b  a为分子，b为分母； 

    int a,b;
  scanf("%d%d",&a,&b);
   if(gcd(a,b)==1)//如果 b（指在gcd函数中 b，是除数，也是最大公约数） 为1
   printf("yesn");
   else printf("non") ;
 } 

这个是我自己根据辗转相除法设计的计算2个数最大公约数的算法代码

//辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。
#include
int main()
{
	int a,b,n,t;
	scanf("%d%d",&a,&b);
	if(a 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5698399.html