鱼C论坛

 找回密码
 立即注册
查看: 2676|回复: 5

求一个数的最大质因数,初始化循环条件我不太懂

[复制链接]
发表于 2016-4-17 23:40:10 | 显示全部楼层 |阅读模式

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

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

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

int main()
{
        unsigned long long i, j, k, max, temp, num = 600851475143;
        _Bool flag = 1;

    temp = (unsigned long long)sqrt((double)num);
        for (i = 2; i <= temp; i++)
        {
                k = (unsigned long long)sqrt((double

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

                if (flag && !(num % i))
                {
                        max = i;
                }
                else
                {
                        flag = 1;
                }
        }

        printf("%llu\n", max);

        return 0;
}






[b   temp = (unsigned long long)sqrt((double)num);
        for (i = 2; i <= temp; i++)[/b]   
为什么要这样循环呢,而不是for(i=2; i<num ;i++)    ,  我们知道 10  的最大质因数是 5  > √10=3????????




而我从另一方面改进算法不知道是否有缺陷,是这样的
初始循环条件改为 for(i=2; i<num ;i++)
在循环内部,判断完 i 是否为质数以后,if语句改为
if(flag&&!( num%i))
{
   max =i;
  num/=i;
}

从这方面缩短迭代的步长。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2016-4-17 23:41:57 | 显示全部楼层
主要解决 迭代结束为什么不到 num,   而直到根号下num?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-18 10:56:35 | 显示全部楼层
数学逻辑:x^2 = x*x;x^2 = x1*x2;显然x1和x2不可能同时大于x,必有一个小于x。所以只要循环到x就能找出x^2的所有因子。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2016-4-18 14:49:13 | 显示全部楼层
LeoChou 发表于 2016-4-18 10:56
数学逻辑:x^2 = x*x;x^2 = x1*x2;显然x1和x2不可能同时大于x,必有一个小于x。所以只要循环到x就能找出x^ ...

那你能保证,大的那个x2 就不是质数了。比如说 10=2*5,26=2*13;
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-4-20 09:39:21 | 显示全部楼层
x1知道了还不知道x2吗?循环控制不是固定死的,完全看你循环里面怎么写。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2016-4-22 10:13:34 | 显示全部楼层
LeoChou 发表于 2016-4-20 09:39
x1知道了还不知道x2吗?循环控制不是固定死的,完全看你循环里面怎么写。

不懂啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-11-27 00:26

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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