[已解决]c语言第一阶段考核第二题

大学里的小菜鸡 · 发表于 2020-8-12 16:13:08

这个是什么算法吗，可以解释一下这个算法吗，求解j的目的是什么
#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;
}

最佳答案

月排行榜 / 总排行榜

baige

2020-8-12 16:13:09

题目只需要找到最大的质数因子，j就是我们要找的数，对于i不用去管

跳转到最佳答案楼层

baige · 发表于 2020-8-12 16:13:09

题目只需要找到最大的质数因子，j就是我们要找的数，对于i不用去管

baige · 发表于 2020-8-12 16:18:20

i*j==num,就说明j是num的因子数，然后就对j进行判断是否是素数

baige · 发表于 2020-8-12 16:26:25

这一部分是判断是不是质数，也就是素数

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

复制代码

这一段主要是判断j是不是num的因子

for (i = 2, j = num/i; flag != 0; i++, j = num/i, flag = 1)
{
if (i * j == num)

复制代码

大学里的小菜鸡 · 发表于 2020-8-12 16:26:27

本帖最后由大学里的小菜鸡于 2020-8-12 16:31 编辑

baige 发表于 2020-8-12 16:18
i*j==num,就说明j是num的因子数，然后就对j进行判断是否是素数

那为什么输出的是i而不是j呢

大学里的小菜鸡 · 发表于 2020-8-12 16:30:27

baige 发表于 2020-8-12 16:26
这一部分是判断是不是质数，也就是素数

这一段主要是判断j是不是num的因子

判断素数和因子懂了，但是不懂输出的为什么是i而不是j

大学里的小菜鸡 · 发表于 2020-8-12 16:33:21

大学里的小菜鸡发表于 2020-8-12 16:26
那为什么输出的是i而不是j呢

它是怎么判断得知i要比j大的

baige · 发表于 2020-8-12 16:39:14

大学里的小菜鸡发表于 2020-8-12 16:33
它是怎么判断得知i要比j大的

答案写错了，应该是j,刚写了个程序判断答案的i不是素数

baige · 发表于 2020-8-12 16:40:41

87625999/71 = 1 234 169

baige · 发表于 2020-8-12 16:41:48

问题解决的话，就结贴吧

大学里的小菜鸡 · 发表于 2020-8-12 16:42:51

baige 发表于 2020-8-12 16:39
答案写错了，应该是j,刚写了个程序判断答案的i不是素数

输出的确实是i比j大，但是是怎么判断的

大学里的小菜鸡 · 发表于 2020-8-12 16:44:42

本帖最后由大学里的小菜鸡于 2020-8-12 16:48 编辑

baige 发表于 2020-8-12 16:39
答案写错了，应该是j,刚写了个程序判断答案的i不是素数

还有他判断了j是质数，i就不用判断是不是质数了吗，还是说这个数比较特殊，确定一个因子是质数了另一个因子就是质数了

baige · 发表于 2020-8-12 16:44:42

大学里的小菜鸡发表于 2020-8-12 16:42
输出的确实是i比j大，但是是怎么判断的

怎么判断什么？

大学里的小菜鸡 · 发表于 2020-8-12 16:46:05

baige 发表于 2020-8-12 16:44
怎么判断什么？

判断i比j大，程序中没有i与j的大小的判断，直接输出i，不用进行i和j的判断吗

baige · 发表于 2020-8-12 16:50:09

大学里的小菜鸡发表于 2020-8-12 16:46
判断i比j大，程序中没有i与j的大小的判断，直接输出i，不用进行i和j的判断吗

不需要，答案就是j, i是小甲鱼打错了而已，
当满足第一个j既是num的因数，又是素数的时候,循环就退出了，此时的j一定是num的最大质数因子，不需要去判断i,j,的大小

大学里的小菜鸡 · 发表于 2020-8-12 16:51:23

baige 发表于 2020-8-12 16:50
不需要，答案就是j, i是小甲鱼打错了而已，
当满足第一个j既是num的因数，又是素数的时候,循环就退出了 ...

不是啊，你输出i和j看看，i的值要比j的值大，j=6857 i=87625999

baige · 发表于 2020-8-12 16:54:47

大学里的小菜鸡发表于 2020-8-12 16:51
不是啊，你输出i和j看看，i的值要比j的值大，j=6857 i=87625999

i一直在累加，如果一直没有符合的情况，i最后一定会比j大很多的，
并且i不是素数，你可以去求一下，我上面已经写了，i可以被71整除

账号		自动登录	找回密码
密码			立即注册