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

1762075716

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

for (l = 2; l <= k; l++)  
                {
                    if (j % l == 0)    
                    {
                        flag = 0;    
                        break;
                    }
                }
                
                if (flag)           
                {
                        break;
                }

这一段的作用应该是判断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
就这点代码实在很难给你解释哟

这是全部代码

#include <stdio.h>
#include <math.h>

int main()
{
    long long i, j, k, l, num = 600851475143;
    _Bool flag = 1;

    for (i = 2, j = num/i; flag != 0; i++, j = num/i, flag = 1)   
    {
            if (i * j == num)      
            {
                k = sqrt((double)j);
                
                for (l = 2; l <= k; l++)  
                {
                    if (j % l == 0)    
                    {
                        flag = 0;    
                        break;
                    }
                }
                
                if (flag)          
                {
                        break;
                }
            }
    }

        printf("%lld\n", j);      

        return 0;
}

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 ...

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