论坛 › C\C++交流 › 请问第一阶段考核这题怎么写？

追光THO 发表于 2022-11-5 07:02:18

请问第一阶段考核这题怎么写？

附上答案，我看不懂，不太理解这题的思路。#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;
}

jhq999 发表于 2022-11-5 08:22:27

#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)//先找到相对最小因子i和相对最大因子j,它们是一一对应的，
                {
                        k = sqrt((double)j);//因为一一对应，所以相对最小因子和相对最大因子最终值是这个数的平方根
                        for (l = 2; l <= k; l++)//判断最大因子是否为质数，能被l整除就不是合数，不是质数，继续取值循环
                        {
                              if (j % l == 0)
                              {
                                        flag = 0;
                                        break;
                              }
                        }
                        if (flag)
                        {
                              break;
                        }
                }
      }

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

      return 0;
}
int main()
{
    unsigned long long num=600851475143,tmp=num,i,j;
    j=(unsigned long long)sqrt((double)tmp);

    for (i=2;i<=j;i+=1)
    {
      if(0==tmp%i)
      {
            tmp=tmp/i;
            i=1;
            j=(unsigned long long)sqrt((double)tmp);
      }
    }
    printf("%llu",tmp);

    return 0;

}

zhangjinxuan 发表于 2022-11-5 09:48:30

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

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

zhangjinxuan 发表于 2022-11-5 09:50:08

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

jackz007 发表于 2022-11-5 10:01:34

本帖最后由 jackz007 于 2022-11-5 10:43 编辑

       i 从 2 开始循环，如果 num 能被 i 整除，那就判断 num / i 是不是一个素数，如果是，那就结束，否则，i ++ 继续，直到找到这个素数为止。
#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)// 从 i = 2 开始循环枚举 num 所有可能的因子
      {
                if (i * j == num)                                    // 如果 num 能够被 i 整除，j 的值是 num / i
                {
                        k = sqrt((double)j);
                        for (l = 2; l <= k; l++)                     // 在 2 ~ sqrt(j) 的范围内枚举 j 的因子
                        {
                              if (j % l == 0)                      // 如果 j 可以被 l 整除，那就说明 j 不是一个素数
                              {
                                        flag = 0 ;                   // 修改标志变量的值
                                        break;                     // 退出内层循环
                              }
                        }
                        if (flag)                                    // 内层循环结束，如果 flag 的值依然是 1，说明 j 是一个素数
                        {
                              break;                               // 那就不用继续找了，直接结束外层循环
                        }
                }
      }
      printf("%lld\n", i);                                       // 【错误】：这里应该打印输出的是 j
      return 0;
}
      这是我写的代码，谨供楼主参考
#include <stdio.h>

int main(void)
{
      long long i , m = 600851475143 ;
      for(i = 2 ; i <= m / i ;) {
                if(! (m % i)) m /= i   ;
                else i ++            ;
      }
      printf("%I64d\n" , m)          ;
}
      编译运行实况：
D:\\C>g++ -o x x.c

D:\\C>x
6857

D:\\C>

追光THO 发表于 2022-11-5 13:57:23

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

查看完整版本: 请问第一阶段考核这题怎么写？