当前位置:网站首页>如何求最大公约数?
如何求最大公约数?
2022-08-09 12:25:00 【进击的李知因】
1、在1~m/2之间找约数,最后的约数即最大公约数
public class Case25_GreatestCommonDivisor{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("请输入两个正整数:");
int m = in.nextInt();
int n = in.nextInt();
int gcd = 1;
if(m>n) //交换,确保m为较小者
{
m = m^n;
n = m^n;
m = m^n;
}
if(m == n || n%m == 0)
{
System.out.printf("%d与%d的最大公约数是%d\n",m,n,m);
System.exit(0);
}
//找约数,最后的即最大公约数
for(int i = 1; i <= m/2; i++)
if(m%i==0 && n%i==0)
gcd = i;
System.out.printf("%d与%d的最大公约数是%d\n",m,n,gcd);
}
}
2、在m/2~1之间找约数,找到就退出循环
for(int i = m/2; i > 0; i--)
if(m%i==0 && n%i==0)
{
gcd = i;
break;
}
3、欧几里德算法(辗转相除法)
public class Case25_GreatestCommonDivisor{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("请输入两个正整数:");
int m = in.nextInt();
int n = in.nextInt();
if(m>n) //交换,确保m为较小者
{
m = m^n;
n = m^n;
m = m^n;
}
while(n%m != 0)
{
int temp = m;
m = n%m;
n = temp;
}
System.out.printf("%d与%d的最大公约数是%d\n",m,n,m);
}
}
边栏推荐
- 00后写个暑假作业,被监控成这笔样
- Rust 入门指南(使用JSON)
- 用皮肤“听”音乐,网友戴上这款装备听音乐会:仿佛住在钢琴里
- 保存Simulink仿真模型为图片或者PDF的方法
- About the handling of variable parameters in the Retrofit network request URL
- go基础之web获取参数
- Rust from entry to proficient 04 - data types
- 8、IDEA提交代码出现: Fetch failed fatal: Could not read from remote repository
- MySQL5.6到8.0的账号迁移
- ansible-cmdb友好展示ansible收集主机信息
猜你喜欢
Simple understanding of ThreadLocal
MySQL principle and optimization of Group By optimization techniques
Fragment中嵌套ViewPager数据空白页异常问题分析
用场景定义硬件,英码科技破解“边缘计算”密码
系统提供的堆 VS 手动改写堆
AI篮球裁判火了,走步算得特别准,就问哈登慌不慌
Do you know the difference between comments, keywords, and identifiers?
Flutter入门进阶之旅(六)Layout Widget
一甲子,正青春,CCF创建六十周年庆典在苏州举行
史上最猛“员工”,疯狂吐槽亿万富翁老板小扎:那么有钱,还总穿着同样的衣服!...
随机推荐
The core key points of microservice architecture
#物联网征文#小熊派设备开发实战
你没见过的《老友记》镜头,AI给补出来了|ECCV 2022
告别手摇织布机的AI时代
Intra-group reverse order adjustment of K nodes
批量读取word docx文件指定表格内容,保存在excel文件中
腾讯发布第二代四足机器人Max,梅花桩上完成跳跃、空翻
The latest interview summary in 20022 brought by Ali senior engineer is too fragrant
Customize VIEW to realize in-app message reminder to rotate up and down
中科院打脸谷歌:普通电脑追上量子优越性,几小时搞定原本要一万年的计算...
流量焦虑背后是企业对客户关系管理的不足
MySQL principle and optimization of Group By optimization techniques
ABAP interview questions: how to use the System CALL interface of the ABAP programming language, direct execution ABAP server operating System's shell command?
用场景定义硬件,英码科技破解“边缘计算”密码
8、IDEA提交代码出现: Fetch failed fatal: Could not read from remote repository
在“Extend the Omniverse”比赛中构建用于 3D 世界的工具
Adalvo收购其首个品牌产品Onsolis
Intranet penetration tool ngrok usage tutorial
工作任务统计
Common gadgets of Shell (sort, uniq, tr, cut)