找到大量最大素数的有效方法

找到大量最大素数的有效方法

从你的方法，你首先生成一个号码的所有约数

n

中

O(n)

，那么你测试这些除数的是另一个主要

O(n)

的呼叫数量

test_prime

（这是无论如何指数）。

更好的方法是观察到，一旦找到一个数的除数，就可以反复除以该数，以消除所有因素。因此，要得到的素数，说

830297

您测试了所有小的素数（缓存的），对于除以您的数的每个素数，请保持除法：

• 830297

  可被整除，

  13

  所以现在您将使用

  830297 / 13 = 63869

• 63869

  仍可被整除

  13

  ，您在

  4913

• 4913

  不除以13，下一个素数就是

  17

  除以

  4913

  得到

  289

• 289

  仍然是的倍数

  17

  ，您拥有

  17

  除数和终止点。

---

为了进一步提高速度，在测试了下面说的缓存素数后

100

，您必须使用

test_prime

函数（根据@Ben的答案更新）来测试素数，但从开始，继续进行反数运算

sqrt

。您的数字可被整除

71

，下一个数字将给出

sqrt

，

91992

该数字在一定程度上接近

6857

最大的素数。