题目：如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。
例如4/3,8/1,1/7， 都是既约分数。
请问（分子和分母都是 1 到 2020 之间的整数）有多少个既约分数？（包括 1和2020）
小玥提示：答案是：
目录
一、基本思路
二、解题方法
三、实现代码
1、辗转相除法
2、结构语句展开暴力解题
一、基本思路
分子和分母的最大公约数是1，那么构成的分数就是既约分数，这是定义。
我们可以尝试列出一些：比如在（1-3）区间，既约分数有：
1/1， 1/2 ，1/3 ，2/1， 2/3 ，3/1， 3/2 一共有7个。
根据上面的例子，你能看出什么规律了吗？
我看出的特点：若分子或者分母只要满足有一个或一个以上是1，那么就是既约分数，同时，分子和分母是互质的（互质，即要求判断两者最大公约数是否为1）。
误区注意：
1、不要把既约分数定义为：分子和分母都是质数的分数。比如15/17也是既约分数，但是15不是质数。
2、比如2/2,3/3,4/4......等等这类的分数不满足条件的，注意区分。
二、解题方法
重点:如何判断分子和分母是否互质？
方法：
1. 求差判断法
先求出它们的差，再判断差与较小的数是否互质。如果互质，则分子和分母一定是互质的。
2. 求商判断法
用大数除以小数，如果除得的余数与其中较小的数互质，则分子和分母是互质的。
3、欧几里得算法——辗转相除法！
欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
（该解释来源于百度，点击蓝字即可跳转）
分析：可以看出上面三种方法，前两种我们很容易理解，像极了我们中学时代解数学题时的思维，但是在我们用代码实现时，这两种方法的代码都比较难写，但不是不可行。
在蓝桥杯比赛中，对我们写的算法是有运行时间和空间大小等等限制的，第三种辗转相除法最好不过了，当然也还有其他更好的方法，总之，没有最优的，只要更优的！！！
三、实现代码
1、辗转相除法
public class count { public static int gcd(int a, int b) //求最大公约数 { if (b == 0) return a; return gcd(b, a % b); } public static void main(String[] args) { int count = 0; for(int i = 1; i <= 5; i++) { for(int j = 1; j <= 5; j++) { if(gcd(i, j) == 1) //最大公约数为1才满足条件 { count++; } } } System.out.println("1-2020之间的既约分数有"+count+"个"); } } 讯享网
运行结果：
2、结构语句展开暴力解题
这个方法，我本来也没有想要去写的，应一位粉丝提问者的要求，小玥写了！
讯享网public class count1 { public static void main(String[] args) { int i,j; //两个游标 int a,b; //构造分数a/b、b/a int count=0; //计数 for(i=1;i<=2020;i++) { for(j=1;j<=2020;j++) { a=i; b=j; if(a!=1 && b!=1) { if(a==b) //遇到2/2,3/3...该类分数，直接跳过 continue; else{ int m=a%b; //相除法，判断a、b是否互质 while(m!=0) { a=b; b=m; m=a%b; } if(b==1) //当m==0和b==1（a、b的最大公约数为1）时，满足条件 { count++; } } } else{ //当a==1或者b==1，以及a=b=1时，是既约分数 count++; } } } System.out.println("1-2020之间的既约分数有"+count+"个"); } }
运行结果：
等风来，不如追风去！！！有任何问题，评论区，小玥期待你的威风走来！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/14790.html