C 代码永远运行*

Question

我试图在 C 中找到一个大数的最大素因数，对于像 100 甚至 10000 这样的小数，它可以正常工作但失败(失败我的意思是它在我的 core2duo 和 i5 上继续运行和运行数十分钟)对于非常大的target数字(请参阅目标数字的代码。 我的算法正确吗？

我是 C 的新手，真的很努力处理大数字。我想要的是更正或指导，而不是我可以使用带有 bignum 绑定和其他东西的 python 来做到这一点(我还没有尝试过，但很确定)，但不能在 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

>任何事情的6000亿次迭代都需要一些不平凡的时间。 您需要大幅减少这种情况。

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

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

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

Answer 2

通过迭代到数字的平方根，我们可以得到它的所有因子。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 3

代码有 2 个主要问题

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

2. 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;
   }
   

Answer 4

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

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 5

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

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

编辑：要测试目标 600,851,475,143 的素数数量约为 7,500,000,000,000，并且表可能会耗尽内存。

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

• 使用unsiged int直到UINT_max的素数

• 将unsigned long long int用于高于该素数的素数

• 使用超过特定内存消耗的暴力破解。

UINT_MAX定义为 4,294,967,295，将覆盖高达 100,000,000,000 的素数，成本为 7.5*4= 30Gb

另请参阅主要页面。