求最大公约数
2021/8/1 23:36:11
本文主要是介绍求最大公约数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一、
最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。
例如: n 和 m 的最大公约数
public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); System.out.println("输入另两个数"); int n=sc.nextInt();//记录n int m=sc.nextInt();//记录m int maxyu =0; for(int i=1;i<=n&&i<=m;i++) { if (n% i == 0 && m% i == 0) { maxyu = i; } } System.out.println(maxyu); }
运行结果:
12 18 6
方法二:(辗转相除法求最大公约数)
欧几里得算法又称辗转相除法,是指用于计算两个非负整数a,b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
辗转辗转相除法:求最大公约数
*1、 如果 b =0 计算结束 a 就是最大公约数
*2、否则 a 除以 b的余数 让a 等于 b, b 等于余数 r
* 3、回到第一步
public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); System.out.println("输入两个数"); int a=sc.nextInt(); int b=sc.nextInt(); int oa=a;//记录原始的a int ob=b;//记录原始的b while(b!=0) { int r=a%b; System.out.println(a+" "+b+" "+r); a=b; b=r; } System.out.println(oa+"和"+ob+"的最大公约数是"+a); }
编译结果为:
输入两个数 12 18 12 18 12 18 12 6 12 6 0 12和18的最大公约数是6
这篇关于求最大公约数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding