//分解质因数
#include<stdio.h>
#include<time.h>
#include<math.h>
int evaluate(int m,int n)
{
int i=2,sum=1;
int count=0;
while(m!=1)//当质因数全部除了原数m之后,结果为1
{
//公约数不会比最小的数大,所以不用考虑比大小
while(m%i==0)//判断是否是因子
{
m=m/i;//i是m的因子的情况下,n除掉i,得到第一个因子,并排除掉本因子对之后的影响
if(n%i==0)//i是否同时是n的因子
{
n=n/i;//i也是n的因子的话,n也除掉i,排除本因子接下来的影响
sum*=i;//公约数的中间数
}
count++;
}
i++;
}
printf("执行次数为: %d\n",count);
return sum;
}
int main()
{
int a,b,ans;
printf("请数入两个整数");
scanf("%d %d",&a,&b);
clock_t start,end;
start=clock();
ans=evaluate(a,b);
end=clock();
printf("用时:%f\n",(double)(end-start));
printf("结果为:%d",ans);
return 0;
}
![](https://profile-avatar.csdnimg.cn/29cd001a1e264fba97e500de3b257efe_weixin_47500703.jpg!4)
分解质因数求公约数,不会求时间复杂度
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
0条回答 默认 最新
悬赏问题
- ¥15 关于#微信#的问题:微信实名不绑卡 可以实现吗 有没有专家 可以解决
- ¥15 (标签-考研|关键词-set)
- ¥15 求修改代码,图书管理系统
- ¥15 请问有没求偏多标签数据集yeast,reference,recreation,scene,health数据集。
- ¥15 传感网应用开发单片机实训
- ¥15 Delphi 关于sAlphaImageList使用问题
- ¥15 寻找将CAJ格式文档转txt文本的方案
- ¥15 shein测试开发会问些啥我是写java的
- ¥15 关于#单片机#的问题:我有个课程项目设计,我想在STM32F103veTX单片机,M3主控模块上设计一个程序,在Keil uVision5(C语言)上代码该怎么编译?(嫌钱少我可以加钱,急急急)
- ¥15 opnet仿真网络协议遇到问题