LG蓝色天空 发表于 2016-4-17 23:40:10

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

#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++)   
为什么要这样循环呢，而不是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;
}

从这方面缩短迭代的步长。

LG蓝色天空 发表于 2016-4-17 23:41:57

主要解决 迭代结束为什么不到 num,   而直到根号下num？

LeoChou 发表于 2016-4-18 10:56:35

数学逻辑：x^2 = x*x；x^2 = x1*x2;显然x1和x2不可能同时大于x，必有一个小于x。所以只要循环到x就能找出x^2的所有因子。

LG蓝色天空 发表于 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；

LeoChou 发表于 2016-4-20 09:39:21

x1知道了还不知道x2吗？循环控制不是固定死的，完全看你循环里面怎么写。

LG蓝色天空 发表于 2016-4-22 10:13:34

LeoChou 发表于 2016-4-20 09:39
x1知道了还不知道x2吗？循环控制不是固定死的，完全看你循环里面怎么写。

不懂啊
页: [1]
查看完整版本: 求一个数的最大质因数，初始化循环条件我不太懂