[已解决]阶段考核的问题

1762075716

求解600851475143的最大质因数的那道题
小甲鱼老师的代码中

1. for (l = 2; l <= k; l++)  
   
2.                 {
   
3.                     if (j % l == 0)   
   
4.                     {
   
5.                         flag = 0;   
   
6.                         break;
   
7.                     }
   
8.                 }
   
9.                
   
10.                 if (flag)           
    
11.                 {
    
12.                         break;
    
13.                 }

复制代码

这一段的作用应该是判断j是不是质数，如果是质数就跳出最外层的循环，然后输出j，那么如何能确定输出的j就是最大质因数呢

最佳答案

月排行榜 / 总排行榜

shuofxz

2017-7-27 23:00:53

1762075716 发表于 2017-7-27 22:42
原题是要求最大质数因子的

这个程序其实是从后往前找因数的，所以第一个找到的就是最大的
你看程序，i虽然是从小到大，但输出的是j，其中 i*j=num  所以，最小的i对应着最大的j
找到第一个符合要求的i，结束循环，将j输出 即为所求

跳转到最佳答案楼层

ba21

就这点代码实在很难给你解释哟

1762075716

ba21 发表于 2017-7-27 22:11
就这点代码实在很难给你解释哟

这是全部代码

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int main()
   
5. {
   
6.     long long i, j, k, l, num = 600851475143;
   
7.     _Bool flag = 1;
   
8. 
   
9.     for (i = 2, j = num/i; flag != 0; i++, j = num/i, flag = 1)   
   
10.     {
    
11.             if (i * j == num)      
    
12.             {
    
13.                 k = sqrt((double)j);
    
14.                
    
15.                 for (l = 2; l <= k; l++)  
    
16.                 {
    
17.                     if (j % l == 0)   
    
18.                     {
    
19.                         flag = 0;   
    
20.                         break;
    
21.                     }
    
22.                 }
    
23.                
    
24.                 if (flag)         
    
25.                 {
    
26.                         break;
    
27.                 }
    
28.             }
    
29.     }
    
30. 
    
31.         printf("%lld\n", j);      
    
32. 
    
33.         return 0;
    
34. }

复制代码

shuofxz

已经是质因数了，还有最大一说么？
（不知道是不是我理解错了）

1762075716

shuofxz 发表于 2017-7-27 22:39
已经是质因数了，还有最大一说么？
（不知道是不是我理解错了）

原题是要求最大质数因子的

shuofxz

1762075716 发表于 2017-7-27 22:42
原题是要求最大质数因子的

这个程序其实是从后往前找因数的，所以第一个找到的就是最大的
你看程序，i虽然是从小到大，但输出的是j，其中 i*j=num  所以，最小的i对应着最大的j
找到第一个符合要求的i，结束循环，将j输出 即为所求

1762075716

shuofxz 发表于 2017-7-27 23:00
这个程序其实是从后往前找因数的，所以第一个找到的就是最大的
你看程序，i虽然是从小到大，但输出的是j ...

原来如此，我可能需要治治眼睛了