[已解决]请问第一阶段考核这题怎么写？

追光THO

附上答案，我看不懂，不太理解这题的思路。

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.                         for (l = 2; l <= k; l++)
    
15.                         {
    
16.                                 if (j % l == 0)
    
17.                                 {
    
18.                                         flag = 0;
    
19.                                         break;
    
20.                                 }
    
21.                         }
    
22.                         if (flag)
    
23.                         {
    
24.                                 break;
    
25.                         }
    
26.                 }
    
27.         }
    
28. 
    
29.         printf("%lld\n", i);
    
30. 
    
31.         return 0;
    
32. }

复制代码

最佳答案

月排行榜 / 总排行榜

jackz007

2022-11-5 10:01:34

       i 从 2 开始循环，如果 num 能被 i 整除，那就判断 num / i 是不是一个素数，如果是，那就结束，否则，i ++ 继续，直到找到这个素数为止。

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)  // 从 i = 2 开始循环枚举 num 所有可能的因子
   
10.         {
    
11.                 if (i * j == num)                                    // 如果 num 能够被 i 整除，j 的值是 num / i
    
12.                 {
    
13.                         k = sqrt((double)j);
    
14.                         for (l = 2; l <= k; l++)                     // 在 2 ~ sqrt(j) 的范围内枚举 j 的因子
    
15.                         {
    
16.                                 if (j % l == 0)                      // 如果 j 可以被 l 整除，那就说明 j 不是一个素数
    
17.                                 {
    
18.                                         flag = 0 ;                   // 修改标志变量的值
    
19.                                         break;                       // 退出内层循环
    
20.                                 }
    
21.                         }
    
22.                         if (flag)                                    // 内层循环结束，如果 flag 的值依然是 1，说明 j 是一个素数
    
23.                         {
    
24.                                 break;                               // 那就不用继续找了，直接结束外层循环
    
25.                         }
    
26.                 }
    
27.         }
    
28.         printf("%lld\n", i);                                         // 【错误】：这里应该打印输出的是 j
    
29.         return 0;
    
30. }

复制代码

        这是我写的代码，谨供楼主参考

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         long long i , m = 600851475143 ;
   
6.         for(i = 2 ; i <= m / i ;) {
   
7.                 if(! (m % i)) m /= i   ;
   
8.                 else i ++              ;
   
9.         }
   
10.         printf("%I64d\n" , m)          ;
    
11. }

复制代码

        编译运行实况：

1. D:\[00.Exerciese.2022]\C>g++ -o x x.c
   
2. 
   
3. D:\[00.Exerciese.2022]\C>x
   
4. 6857
   
5. 
   
6. D:\[00.Exerciese.2022]\C>

复制代码

跳转到最佳答案楼层

jhq999

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)//先找到相对最小因子i和相对最大因子j,它们是一一对应的，
    
12.                 {
    
13.                         k = sqrt((double)j);//因为一一对应，所以相对最小因子和相对最大因子最终值是这个数的平方根
    
14.                         for (l = 2; l <= k; l++)//判断最大因子是否为质数，能被l整除就不是合数，不是质数，继续取值循环
    
15.                         {
    
16.                                 if (j % l == 0)
    
17.                                 {
    
18.                                         flag = 0;
    
19.                                         break;
    
20.                                 }
    
21.                         }
    
22.                         if (flag)
    
23.                         {
    
24.                                 break;
    
25.                         }
    
26.                 }
    
27.         }
    
28. 
    
29.         printf("%lld\n", i);
    
30. 
    
31.         return 0;
    
32. }

复制代码

1. int main()
   
2. {
   
3.     unsigned long long num=600851475143,tmp=num,i,j;
   
4.     j=(unsigned long long)sqrt((double)tmp);
   
5. 
   
6.     for (i=2;i<=j;i+=1)
   
7.     {
   
8.         if(0==tmp%i)
   
9.         {
   
10.             tmp=tmp/i;
    
11.             i=1;
    
12.             j=(unsigned long long)sqrt((double)tmp);
    
13.         }
    
14.     }
    
15.     printf("%llu",tmp);
    
16. 
    
17.     return 0;
    
18. 
    
19. }

复制代码

zhangjinxuan

答案其实写的很麻烦，这是我的答案：

1. 
   
2. #include <stdio.h>
   
3. long long max(long long a, long long b) { //最大值
   
4.         return a > b ? a : b;
   
5. }
   
6. long long num = 600851475143, res = 0; //初始化变量
   
7. int main() {
   
8.         for (long long i = 2; i * i <= num; ++i) {   //num的所有质因数都是不大于sqrt(num)的，这是验证过的
   
9.                 while (num % i == 0) { //直到num不是i的因数
   
10.                         res = max(res, i);  //更新答案
    
11.                         //printf("%d ", i);
    
12.                         num /= i;
    
13.                 }
    
14.                 //当程序执行到这里，num不是 i 的因数，num也不是 i * 2 的倍数，这种做法需要一点数学功底
    
15.         }
    
16.         if (num > 1) {  //如果num > 1，说明num已经被除成质数了，也要更新答案
    
17.                 res = max(res, num);
    
18.                 //printf("%d ", num);
    
19.         }
    
20.         printf("%lld", res); //答案输出
    
21. }

复制代码

没有必要unsigned long long，不会溢出

zhangjinxuan

答案其实错了，要知道，87625999也不是一个质数

jackz007

       i 从 2 开始循环，如果 num 能被 i 整除，那就判断 num / i 是不是一个素数，如果是，那就结束，否则，i ++ 继续，直到找到这个素数为止。

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)  // 从 i = 2 开始循环枚举 num 所有可能的因子
   
10.         {
    
11.                 if (i * j == num)                                    // 如果 num 能够被 i 整除，j 的值是 num / i
    
12.                 {
    
13.                         k = sqrt((double)j);
    
14.                         for (l = 2; l <= k; l++)                     // 在 2 ~ sqrt(j) 的范围内枚举 j 的因子
    
15.                         {
    
16.                                 if (j % l == 0)                      // 如果 j 可以被 l 整除，那就说明 j 不是一个素数
    
17.                                 {
    
18.                                         flag = 0 ;                   // 修改标志变量的值
    
19.                                         break;                       // 退出内层循环
    
20.                                 }
    
21.                         }
    
22.                         if (flag)                                    // 内层循环结束，如果 flag 的值依然是 1，说明 j 是一个素数
    
23.                         {
    
24.                                 break;                               // 那就不用继续找了，直接结束外层循环
    
25.                         }
    
26.                 }
    
27.         }
    
28.         printf("%lld\n", i);                                         // 【错误】：这里应该打印输出的是 j
    
29.         return 0;
    
30. }

复制代码

        这是我写的代码，谨供楼主参考

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         long long i , m = 600851475143 ;
   
6.         for(i = 2 ; i <= m / i ;) {
   
7.                 if(! (m % i)) m /= i   ;
   
8.                 else i ++              ;
   
9.         }
   
10.         printf("%I64d\n" , m)          ;
    
11. }

复制代码

        编译运行实况：

1. D:\[00.Exerciese.2022]\C>g++ -o x x.c
   
2. 
   
3. D:\[00.Exerciese.2022]\C>x
   
4. 6857
   
5. 
   
6. D:\[00.Exerciese.2022]\C>

复制代码

追光THO

感谢大家，这题我已经看懂了