鱼C论坛

 找回密码
 立即注册
查看: 2515|回复: 0

[学习笔记] 关于小甲鱼阶段考核测试答案中代码结果不正确讨论

[复制链接]
发表于 2023-2-15 14:05:09 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本题目要求是求出6008514751432的最大质子因数,小甲鱼代码如下:

#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;
}

该代码结果87625999,对该数进行质数检查,结果检查得出该数不是一个质数,即不满足题目要求;

其实按照数学逻辑来讲是不需要对除数做一个质数判断的,上述代码出发点存在一定的问题,首先我们定义的计数器'i'也就是除数是从2这个数开始递增的,初始化数2本身属于一个质数,当判断num%2!=0时,其实我们已经可以得到结论,该数没有质数因子2,当num%3!=0时,同样得到结论,该数没有质数因子3。由此我们发现假如一个num没有质数因子2和3时,那么必然有num%(2^n*3^n)!=0(n为自然数)。

因此我们对num直接从2递增循环做余数判断,如果余数为0,即证明i为其因数,并临时存贮num/(i^n)和i的结果,循环相除,所有因数被除以后,直到得到最后的num=1,那么他的上一次存贮的i即为最大质数因子;代码如下:
#include<stdio.h>
#include<math.h>

int main()
{
        long long num=600851475143,temp;
        double j;
        int k=1;
       
        j=pow(num,0.5);
       
        for(int i=2;i<=j;i++)
        {
                if(num%i==0)
                {
                        temp=i;
                        while(!(num%i))
                        {
                                num=num/i;
                        }
                }
        }
        printf("%d\n",temp);
       
        return 0;
       
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-24 07:04

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表