严凯 发表于 2020-11-22 10:32:51

有点困难问题求助

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

int main()
{
      long long i, j, k, l, num = 600851475143;
      int 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;
}

// 编写一个程序，求解 600851475143 的最大质数因子是多少？
每个合数都可以写成几个质数（素数）相乘的形式，这几个质数就都叫做这个合数的质数因子。
比如 13195 的质数因子有 5, 7, 13 和 29


//这个完全看不懂啊。。。。。。

jackz007 发表于 2020-11-22 11:00:10

请参考此贴：https://fishc.com.cn/forum.php?mod=redirect&goto=findpost&ptid=184779&pid=5101451&mobile=2

风过无痕1989 发表于 2020-11-23 14:23:20

本帖最后由 风过无痕1989 于 2020-11-23 20:10 编辑

下面的程序，8 位数我验证了，没有问题，给你作个参考。long long 类型我就不去运算，你自己改后去运算。
#include<stdio.h>
#include<math.h>
int main()
{
        int prime(int num);
        int i, j, k, num = 999999999;   // 9 个 9 是我的系统的 int 能运行的最大的数了，运行时间超长、难等
                                        // 超过这个数，就要用 long，或者 long long
        for (i = sqrt(num);i > 0;i--)
        {
                for (j = 2;j < sqrt(num);j++)
                {
                        if (i * j == num)
                        {
                                k = prime(i);
                                if (k == 1)
                                {
                                        printf("%d 最大的质数因子是：%d\n", num,i);
                                        break;
                                }
                        }

                }
        }
}

int prime(int num)          // 判断质数
{
        int i, y = 0;
        for (i = 2;i < num;i++)
        {
                if (num % i == 0)
                {
                        break;
                }
                else if (i >= sqrt(num))
                {
                        y = 1;
                        break;
                }
        }
        return y;
}

风过无痕1989 发表于 2020-11-23 20:09:10

回过头来再看这一题，第8行可改为：for (i = sqrt(num);i > 0;i--) ,以进一步缩短运行时间
页: [1]
查看完整版本: 有点困难问题求助