algorithm - 什么是最有效的给出素数的算法，最高值(所有 32 位机器都可以处理)

Question

我的程序应该永远循环并通过打印给出它出现的每个质数。顺便说一句，在 x86-NASM 中执行此操作。

我的第一次尝试将它除以之前的每个数字，直到进位为 0(不是质数)或结果为 1。

我的第二次尝试改进了这一点，每秒只测试一次，所以只测试奇数。

我目前正在实现的第三件事是尝试不除以每个先前的数字，而是将所有先前的数字除以 2，因为您不能通过将一个数字除以大于其一半的数字来得到偶数

另一件可能有帮助的事情是只用奇数来测试它，比如埃拉托色尼筛法，但只排除偶数。

无论如何，如果还有什么我可以做的，欢迎大家帮忙。

编辑:

Answer 1

如果您需要测试少数几个(可能只有一个)素数，则 AKS primality test是 n 长度的多项式。
如果你想找到一个非常大的密码大小的素数，然后选择一个随机范围的奇数并筛选出所有因子为小素数(例如小于 64K-240K)的数字，然后测试剩余数字的素数。

如果你想找到一个范围内的素数那么use a sieve , Erathostenes 的筛子很容易实现，但运行速度较慢并且需要更多内存。
sieve of Atkin更快，wheels sieve需要更少的内存。

如果天真地接近问题的规模是指数级的，所以在微观优化之前必须先进行宏观优化。
或多或少，所有素数算法都需要对 Number theory 有信心，所以要特别注意算法正在处理的组/环/域，因为数学家会为所有代数结构编写诸如逆运算或乘法之类的运算，并使用相同的符号。

一旦你有了一个快速的算法，你就可以开始微观优化了。
在这个层面上，真的不可能回答如何进行这样的优化。