[已解决]C语言编程遇到的问题

fishc098

求出num的最大质数因子。

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int main()
   
5. {
   
6.     long long i, j, k, num = 600851475143;
   
7.     _Bool flag1 = 1;//判断质数
   
8.     _Bool flag2 = 0;//判断约数
   
9.        
   
10.     for (i = num; i > 2; i--)
    
11.     {
    
12.         if (num % i == 0)
    
13.         {
    
14.                 flag2 = 1;
    
15.             k = sqrt((double)i);
    
16.             for (j = 2; j <= k; j++)
    
17.             {
    
18.                 if (i % j == 0)
    
19.                 {
    
20.                     flag1 = 0;
    
21.                     break;
    
22.                 }
    
23.             }
    
24.             if (flag1 == 1 && flag2 == 1)
    
25.             {
    
26.                 break;
    
27.             }
    
28.             else
    
29.             {
    
30.                     flag2 = 0;
    
31.                     flag1 = 1;
    
32.                         }
    
33.         }
    
34.     }
    
35. 
    
36.     printf("最大质数因子为%lld\n", i);
    
37. 
    
38.     return 0;
    
39. }

复制代码

运行没有结果
哪位大神帮忙看看错误在哪，并给出修改建议。

最佳答案

月排行榜 / 总排行榜

micolar

2019-7-22 20:33:38

思路没问题  
应该是超时吧
你那个不用从600851475143判断
假设一下 如果有一个数10000 那么这个数的最大质因子要么它本身 要么小于等于他的根号也就是100 这个你要想一下为什么比较好
题目说了 它是合数 所以不用判断它是否是质数
所以我判断1000000内的数就可以了

那个欧拉计划我也有做过这道题

#include<stdio.h>
int a[1000001];
int main(){
        int i,j;
        for(i = 2; i <= 500000;i++){
                for(j = i * 2;j <=1000000;j += i)
                        a[j] = 1;
        }
        for(i = 999999;i >= 2; i-- )
        if(a[i] == 0 && 600851475143%i == 0){
                printf("%d",i);
                return 0;
        }
        
        printf("600851475143");
        
        return 0;
}

我是先筛选素数在判断是不是因子
筛选素数的思路很简单 素数的倍数不是素数 用数组辅助  求得一定范围内的素数然后判断

跳转到最佳答案楼层

一木之禾

如果我没有理解错的话，应该是这里有问题，上面第一个break意思是找到了答案吧，那时候你的flag1赋值为0，下面这里却判断它是不是为1，那当然就跳不出循环了。你想一下，修改修改。

1. if (flag1 == 1 && flag2 == 1)
   
2.             {
   
3.                 break;
   
4.             }

复制代码

micolar

思路没问题  
应该是超时吧
你那个不用从600851475143判断
假设一下 如果有一个数10000 那么这个数的最大质因子要么它本身 要么小于等于他的根号也就是100 这个你要想一下为什么比较好
题目说了 它是合数 所以不用判断它是否是质数
所以我判断1000000内的数就可以了

那个欧拉计划我也有做过这道题

#include<stdio.h>
int a[1000001];
int main(){
        int i,j;
        for(i = 2; i <= 500000;i++){
                for(j = i * 2;j <=1000000;j += i)
                        a[j] = 1;
        }
        for(i = 999999;i >= 2; i-- )
        if(a[i] == 0 && 600851475143%i == 0){
                printf("%d",i);
                return 0;
        }
        
        printf("600851475143");
        
        return 0;
}

我是先筛选素数在判断是不是因子
筛选素数的思路很简单 素数的倍数不是素数 用数组辅助  求得一定范围内的素数然后判断

micolar

我帮你试了 你把i的范围改小一点就可以了 要大于等于sqrt( 600851475143) （我用的是1000000）
答案就出了

micolar

然后我也发现我的错误 我做多余了 判断素数还不如判断因子来的快 谢谢

fishc098

谢谢大家的帮助，我已经得出结果啦！
代码修改如下

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int main()
   
5. {
   
6.     long long i,max,num = 600851475143;
   
7.         
   
8.     for (i = 2; i <= sqrt((double)num); i++)//从2到根号n求其质因数
   
9.     {
   
10.         while(num % i == 0)//因为一个质因数可能会乘多次，所以应该用while，而不是if
    
11.         {
    
12.                 max = i;                //让max指向当前最大值
    
13.                 num /= i;                //除以质因数
    
14.                 }
    
15.                 if(1 == num)
    
16.                 break;
    
17.     }
    
18.    
    
19.     if(num != 1)//如果n不等于1，说明存在一个大于根号num的质因数，有且仅有一个，即等于当前的num
    
20.     max = num;
    
21. 
    
22.     printf("最大质数因子为%lld\n", max);
    
23. 
    
24.     return 0;
    
25. }

复制代码

fishc098

这种算法可以很好地提高程序运行效率，但是其中的思想我不是很能理解，希望能够互相交流学习！