[已解决]第一阶段考核的第2题，不知解题思路，答案看不懂

Sparin

题目：编写一个程序，求解 600851475143 的最大质数因子是多少？
（每个合数都可以写成几个质数（素数）相乘的形式，这几个质数就都叫做这个合数的质数因子。
比如 13195 的质数因子有 5, 7, 13 和 29。）
1.能否说下该如何设计该程序？（解题思路）
2.解析下答案为何要这样做？（越全面越好）
答案：
#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", i);

        return 0;
}

最佳答案

月排行榜 / 总排行榜

召唤风云

2020-2-7 22:16:15

第1问，如果是我，我会这样做。用一个for循环i从一到原来的那个数,看i是不是原来的数的因数,如果是那就break。那么i一定是一个质数。用原来的数除以i，得到一个新的数。编写一个函数，用来检测一个数是否是质数。检测新的数是否是质数,如果不是,重复上述操作,只要把原来的数换成新的数。如果新的数是质数(新的数肯定比被除掉的数更大)，那么新的数就是所求的解(所以新的数是最大的因数)。第2问，那个代码好像就是这种意思。(当你遇到一段代码的时候，先想想自己会怎么做。然后按照你自己的想法推测于原来的代码的作用，你就看得懂代码了)

跳转到最佳答案楼层

召唤风云

第1问，如果是我，我会这样做。用一个for循环i从一到原来的那个数,看i是不是原来的数的因数,如果是那就break。那么i一定是一个质数。用原来的数除以i，得到一个新的数。编写一个函数，用来检测一个数是否是质数。检测新的数是否是质数,如果不是,重复上述操作,只要把原来的数换成新的数。如果新的数是质数(新的数肯定比被除掉的数更大)，那么新的数就是所求的解(所以新的数是最大的因数)。第2问，那个代码好像就是这种意思。(当你遇到一段代码的时候，先想想自己会怎么做。然后按照你自己的想法推测于原来的代码的作用，你就看得懂代码了)

召唤风云

好吧，这段代码和我的想法有很大的不同。他是反过来想的

召唤风云

一个数由两个数相乘。让一个数最小，那么另一个数就是最大。如果最大的这个数是合数，说明他应该更小一点。那么让这个小的数更大一点就OK了，直到最大更大的那个数是质数。中间的一段代码都是判断该数是不是质数。

Sparin

召唤风云 发表于 2020-2-7 23:22
一个数由两个数相乘。让一个数最小，那么另一个数就是最大。如果最大的这个数是合数，说明他应该更小一点。 ...

1.if (j % l == 0)
{
             flag = 0;
            break;
}//这段不是表示，J是合数就break吗？
2.printf("%lld\n", i);//为什么是输出变量i，i不是从最小的开始吗？

召唤风云

第1问,如果j是合数，就不要它了。这就是flag的作用。第2问。把35,105带进去。发现应该输出j而不是i。但是我复制的时候有一个问题。我也不知道是什么原因。num的值永远都是0,然后我只能用宏定义，就好了。

召唤风云

如果你觉得你没问题，那就是代码有问题。

坑得飞起

n的质数因子<=n的平方根，n=600851475143，平方根<800000，穷举出来答案不费什么时间空间

wp231957

我只知道答案，、、因子是：[71, 839, 1471, 6857]

Sparin

召唤风云 发表于 2020-2-8 13:00
第1问,如果j是合数，就不要它了。这就是flag的作用。第2问。把35,105带进去。发现应该输出j而不是i。但是我 ...

因为num被定义为long long，所以在编译的时候应该加上 -std=c99

Sparin

坑得飞起 发表于 2020-2-8 16:00
n的质数因子

确实也是种思路，谢谢o(*￣▽￣*)o

Sparin

召唤风云 发表于 2020-2-8 13:00
第1问,如果j是合数，就不要它了。这就是flag的作用。第2问。把35,105带进去。发现应该输出j而不是i。但是我 ...

for循环体的条件是（flag ！=0），应该可理解为当flag为1时就循环下去，为0时跳出来输出结果把，这里J是合数，令flag等于0，我想的是，它会直接终止这个大循环，直接输出结果？
那你认为flag的作用是什么？

SHRS23

代码有问题，输入15的预期输出是5，实际输出3

这个题的解题思路实际上是分解质因数，属于学编程的经典题了
解法解析也有很多可以自己搜索资料
参考：https://blog.csdn.net/mrbourne/article/details/20315123

解决了分解质因数的问题，求最大就很容易了

召唤风云

for (i = 2, j = num/i; flag != 0; i++, j = num/i, ★flag = 1★),所以flag != 0没用。只有if (flag)
                        {
                                break;
                        }
这句才可以终止循环。只有素数可以

Sparin

召唤风云 发表于 2020-2-8 19:09
for (i = 2, j = num/i; flag != 0; i++, j = num/i, ★flag = 1★),所以flag != 0没用。只有if (flag)
   ...

就是说：flag = 0；break；这句可理解为：flag = 0 ；flag = 1；break；这样吗？

召唤风云

Sparin 发表于 2020-2-9 15:02
就是说：flag = 0；break；这句可理解为：flag = 0 ；flag = 1；break；这样吗？

注意看循环最后一句。先执行flag=1,再判断,flag!=0,所以循环一定会继续。只有if (flag)
                        {
                                break;
                        }
这句才可以终止循环。只有素数可以。上面循环判断的条件，可以说根本就没有用。最后一句让flag重新等于1。反正这句话的作用就是这样。一定是只有素数他才可以得到最终结果。

Sparin

召唤风云 发表于 2020-2-9 15:25
注意看循环最后一句。先执行flag=1,再判断,flag!=0,所以循环一定会继续。只有if (flag)
                ...

在for语句里不是先判断再进行循环吗？

Sparin

SHRS23 发表于 2020-2-8 19:04
代码有问题，输入15的预期输出是5，实际输出3

这个题的解题思路实际上是分解质因数，属于学编程的经典题 ...

还要质因数是素数，思路是不是找个循环体从2开始除，等除数等于自身，余数才为0时才跳出循环，否则再将商作为被除数继续进入这个循环体，可以这样理解吗？

召唤风云

Sparin 发表于 2020-2-9 15:33
在for语句里不是先判断再进行循环吗？

for(a;b;c){d}。先进行a。再判断b。不成立则循环终止。成立就执行d。然后执行c。再判断b。然后就是重复。

SHRS23

Sparin 发表于 2020-2-9 15:37
还要质因数是素数，思路是不是找个循环体从2开始除，等除数等于自身，余数才为0时才跳出循环，否则再将商 ...

质数就是素数，是这意思