C语言编程遇到的问题
求出num的最大质数因子。#include <stdio.h>
#include <math.h>
int main()
{
long long i, j, k, num = 600851475143;
_Bool flag1 = 1;//判断质数
_Bool flag2 = 0;//判断约数
for (i = num; i > 2; i--)
{
if (num % i == 0)
{
flag2 = 1;
k = sqrt((double)i);
for (j = 2; j <= k; j++)
{
if (i % j == 0)
{
flag1 = 0;
break;
}
}
if (flag1 == 1 && flag2 == 1)
{
break;
}
else
{
flag2 = 0;
flag1 = 1;
}
}
}
printf("最大质数因子为%lld\n", i);
return 0;
}
运行没有结果{:10_254:}
哪位大神帮忙看看错误在哪，并给出修改建议。 如果我没有理解错的话，应该是这里有问题，上面第一个break意思是找到了答案吧，那时候你的flag1赋值为0，下面这里却判断它是不是为1，那当然就跳不出循环了。你想一下，修改修改。
if (flag1 == 1 && flag2 == 1)
{
break;
} 思路没问题
应该是超时吧
你那个不用从600851475143判断
假设一下 如果有一个数10000 那么这个数的最大质因子要么它本身 要么小于等于他的根号也就是100 这个你要想一下为什么比较好
题目说了 它是合数 所以不用判断它是否是质数
所以我判断1000000内的数就可以了
那个欧拉计划我也有做过这道题
#include<stdio.h>
int a;
int main(){
int i,j;
for(i = 2; i <= 500000;i++){
for(j = i * 2;j <=1000000;j += i)
a = 1;
}
for(i = 999999;i >= 2; i-- )
if(a == 0 && 600851475143%i == 0){
printf("%d",i);
return 0;
}
printf("600851475143");
return 0;
}
我是先筛选素数在判断是不是因子
筛选素数的思路很简单 素数的倍数不是素数 用数组辅助求得一定范围内的素数然后判断 我帮你试了 你把i的范围改小一点就可以了 要大于等于sqrt( 600851475143) （我用的是1000000）
答案就出了 然后我也发现我的错误 我做多余了 判断素数还不如判断因子来的快 谢谢 本帖最后由 fishc098 于 2019-7-23 11:14 编辑
谢谢大家的帮助，我已经得出结果啦！
代码修改如下
#include <stdio.h>
#include <math.h>
int main()
{
long long i,max,num = 600851475143;
for (i = 2; i <= sqrt((double)num); i++)//从2到根号n求其质因数
{
while(num % i == 0)//因为一个质因数可能会乘多次，所以应该用while，而不是if
{
max = i; //让max指向当前最大值
num /= i; //除以质因数
}
if(1 == num)
break;
}
if(num != 1)//如果n不等于1，说明存在一个大于根号num的质因数，有且仅有一个，即等于当前的num
max = num;
printf("最大质数因子为%lld\n", max);
return 0;
} 这种算法可以很好地提高程序运行效率，但是其中的思想我不是很能理解，希望能够互相交流学习！
页:
[1]