C 代码永远保持运行*

Question

我试图在 C 中找到一个巨大数字的最大质因数，对于像 100 甚至 10000 这样的小数字，它工作正常但失败了（失败我的意思是它保持 运行和运行 在我的 core2duo 和 i5 上持续数十分钟）对于非常大的 target 数字（参见目标数字的代码。）我的算法正确吗？

我是 C 语言的新手，在处理大数方面确实很吃力。我想要的是更正或指导而不是解决方案我可以使用 python 和 bignum 绑定和东西来做到这一点（我还没有尝试过但我很确定）但不是在 C . 或者我可能犯了一些我太累而没有意识到的小错误，无论如何这是我写的代码：

#include <stdio.h>
// To find largest prime factor of target
int is_prime(unsigned long long int num);

long int main(void) {
    unsigned long long int target = 600851475143;
    unsigned long long int current_factor = 1;
    register unsigned long long int i = 2;
    while (i < target) {
        if ( (target % i) == 0  && is_prime(i) && (i > current_factor) ) { //verify i as a prime factor and greater than last factor
            current_factor = i;
        }
        i++;
    }
    printf("The greates is: %llu \n",current_factor);
return(0);
}


int is_prime (unsigned long long int num) { //if num is prime 1 else 0 
    unsigned long long int z = 2;
    while (num > z && z !=num) {
        if ((num % z) == 0) {return 0;}
        z++;
    }

return 1;
}

Answer 1

通过迭代直到数字的平方根，我们可以获得它的所有因子。（factor 和 N/factor 和 factor<=sqrt(N)）。在这个小想法下，存在解决方案。任何小于我们检查的 sqrt(N) 的因子，都会有对应的大于 sqrt(N) 的因子。所以我们只需要检查到sqrt(N)，然后我们就可以得到剩下的因素。

在这里您不需要明确使用任何素数查找算法。分解逻辑本身将推断目标是否为质数。所以剩下的就是检查成对因素。

unsigned long long ans ;
for(unsigned long long i = 2; i<=target/i; i++)
   while(target % i == 0){ 
      ans = i; 
      target/=i;
   }

if( target > 1 ) ans = target; // that means target is a prime.
//print ans

^{编辑：要添加的一点（chux）- i*i 在早期的代码中可能会导致溢出，如果我们使用 i<=target/i.}

^{另外一个选择是}

unsigned long long sqaure_root = isqrt(target);
for(unsigned long long i = 2; i<=square_root; i++){
 ...
}

这里注意使用 sqrt 不是一个明智的选择，因为 - 将双精度数学运算与整数运算混合使用很容易出现舍入错误。

对于给定的目标，答案将是 6857。

Answer 2

is_prime 有一个先有鸡还是先有蛋的问题，因为您只需要针对其他素数来测试 num。所以你不需要检查 9，因为它是 3 的倍数。

is_prime 可以维护一个素数数组，每次测试一个新的 num 是一个质数时，它可以添加到数组中。 num 针对数组中的每个素数进行测试，如果它不能被数组中的任何素数整除，则它本身就是一个素数并被添加到数组中。 aray 需要 malloc'd 和 relloc'd 除非有一个公式来计算你的目标的素数（我相信这样的公式不存在）。

编辑：要测试目标 600,851,475,143 的质数数量约为 7,500,000,000，table 可能运行内存不足。

可以按如下方式调整该方法：

使用 unsiged int 直到 UINT_max
使用 unsigned long long int 用于高于该值的素数
在一定内存消耗以上使用暴力破解。

UINT_MAX 被定义为 4,294,967,295 并且将涵盖最多约 100,000,000,000 的质数，并且将花费 7.5*4= 30Gb

另见 The Prime Pages。

Answer 3

没有错，只是需要优化，例如：

int    is_prime(unsigned long long int num) { 
    if (num == 2) {
        return (1);                /* Special case */
    }
    if (num % 2 == 0 || num <= 1) {
         return (0);
    }
    unsigned long long int z = 3;  /* We skipped the all even numbers */
    while (z < num) {              /* Do a single test instead of your redundant ones */
        if ((num % z) == 0) {
            return 0;
        }
        z += 2;                     /* Here we go twice as fast */
    }
return 1;
}

另外一个大问题是 while (z < num) 但由于您不想要解决方案，我让您找到如何优化它，同样自己查看第一个函数。

编辑：有人在我之前 50 秒发布了素数数组列表的解决方案，这是最好的，但我选择提供一个简单的解决方案，因为你只是一个初学者，一开始操作数组可能并不容易（需要学习指针和东西）。

Answer 4

任何事物的 6000 亿次迭代都将花费一些不平凡的时间。你需要大幅减少它。

这里有一个提示：给定一个任意整数值 x，如果我们发现 y 是一个因数，那么我们就隐含地发现 x / y 也是一个因数。换句话说，因素总是成对出现的。因此，在进行冗余工作之前，我们需要迭代多远是有限制的。

那个限制是多少？那么，y 大于 x / y 的交叉点是多少？

将此优化应用于外循环后，您会发现代码的运行时间将受到 is_prime 函数的限制。当然，你也可以应用类似的技术。

Answer 5

代码有 2 个主要问题

while (i < target) 循环效率很低。找到一个因子后，target 可以减少为 target = target / i;。此外，因素 i 可能会出现多次。修复未显示。

is_prime(n) 效率很低。它的 while (num > z && z !=num) 可以循环 n 次。这里也使用商将迭代限制为 sqrt(n) 次。

int is_prime (unsigned long long int num) {
  unsigned long long int z = 2;
  while (z <= num/z) {
    if ((num % z) == 0) return 0;
    z++;
  }
  return num > 1;
}

C 代码永远保持运行*

C code keeps running forever*

c

long-integer

C 代码永远保持 运行*

C code keeps running forever*

c

long-integer

C 代码永远保持运行*