关于如何使我的算法更快的建议
这是我在C中的代码来自项目-Euler的问题＃3，在那里我必须找到最大的素数因子600851475143。
#include #include bool is_prime(long int number){ long int j; for (j=2; j1; factor--){ if (input%factor==0 && is_prime(factor)) { ans = factor; break; } } printf("%d\n", ans); system("pause"); return 0; } 虽然它适用于小数字，但逐渐需要花费越来越多的时间来给出答案。 最后，对于600851475143，代码返回0，这显然是错误的。 有人可以帮忙吗？ 非常感谢。
需要考虑的一些事项：
-
正如@Alex Reynolds所指出的那样，你想要考虑的数字可能是如此之大，以至于它无法适应
int。 您可能需要使用long或uint64_t来存储该数字。 仅这一点就可以解决问题。 -
您可能不想检查每个除数并查看哪些是素数，而是想尝试这种方法：将n设置为600851475143。对于从2向上的每个整数，尝试将n除以该整数。 如果它干净地分开，则从n中除去该数字的所有副本，并将最大的素因子记录为当前整数。 如果你仔细想一想，你会发现你用这种方式考虑的唯一除数就是素数。 作为一个有用的提示 – 如果n没有小于√n的除数（除了1），那么它就是素数。 这可能会帮助您在搜索空间中获得比您正在使用的两个技巧更加紧密的上限。
-
不要将除数增加1，尝试将2作为除数测试，然后仅除以奇数（3,5,7,9,11等）除了2以外的偶数是素数，所以这个数量减半您需要除以的数字。
或者，通过从互联网下载素数列表创建一个存储所有素数达√600851475143的文件，然后测试每个素数以查看是否有任何素数除以600851475143并取最大值。 🙂
希望这可以帮助！
我建议你改进你的代码的素性检查部分。 你的方法的运行时间是O（n 2 ）所以你应该使用一个更有效的算法，就像众所周知的Miller-Rabin素数测试用O（klog 3 n） 。 我在这里为您提供伪代码，您可以自己编写代码：
输入：n> 3，一个要测试素数的奇数;
输入：k，确定测试准确性的参数
输出：复合，如果n是复合，否则可能是素数
将n - 1写为2s·d，其中d为奇数，从n - 1中分解2的幂
WitnessLoop：重复k次：
选择[2，n - 2]范围内的随机整数a
x←ad mod n
如果x = 1或x = n - 1则执行下一个WitnessLoop
重复s - 1次：
x←x2 mod n
如果x = 1则返回复合
如果x = n - 1则执行下一个WitnessLoop
返回复合
回归可能是素数
我提供了一个链接，供您在python中查看实现，并将此算法与您的算法进行比较。 顺便说一句，这个算法在网络上有很多实现，但我认为自己正确对它可以帮助你更好地理解它。
请尝试以下代码。 它基本上实现了接受答案中的要点。 唯一的改进是它使用车轮分解来跳过所有的2,3和5的倍数http://en.wikipedia.org/wiki/Wheel_factorization
//find largest prime factor for x <2^64 #include #include int main() { uint64_t x = 600851475143; int wheel[] = {4,2,4,2,4,6,2,6}; while(x>2 && x%2==0) x/=2; while(x>3 && x%3==0) x/=3; while(x>5 && x%5==0) x/=5; for(uint64_t j=0, i=7; i<=x/i; i+=wheel[j++], j%=8) { while(x>i && x%i==0) x/=i; } printf("%llu\n", x); }
可以做的另一件事是预先计算小于2 ^ 32的所有素数（而不是下载它们）然后仅除以素数。 我所知道的最快的方法是Eratosthenes筛选 。 这是一个使用OpenMP的版本，可以在不到一秒的时间内找到高达10亿的素数.http ：//create.stephan-brumme.com/eratosthenes/