我已经搜索了确定一个数字是否是素数的方法，但大多数方法要么是概率性的(Miller Rabin(，要么是小于64位的数字。
另一种解决方案是使用蛮力方法进行一些改进或筛子，但是当数字超过64位阈值时，这两种方法都不是很有效。
您要查找的内容不存在。没有简单的确定性素数检验始终适用于所有整数范围。
你已经知道米勒-拉宾测试了。它可以在特定范围内确定;有关详细信息，请参阅此处或此处。如果你假设黎曼猜想，那么如果 n 是所有整数 a 的 a-SPRP(米勒强伪素数(，则 n 是素数，<</em>a<2(logn(²。一个类似且更好的测试是贝利-瓦格斯塔夫测试;它不是确定性的，但已知没有故障。
对于数字 n到 2128，分解n− 1 并使用 Pocklington 检验来证明素数并不难。您可以使用试验除法、波拉德 rho 或 ECM 来执行因子分解。还有一些测试(BLS75(可以证明基于部分分解的素数。较大的n也可以使用Pocklington检验来证明是素数，尽管有时因式分解变得困难。
对于n到大约101000，快速ECPP素数测试并非不合理，尽管对于该范围内的较大数字可能需要一段时间。除此之外，除非你的号码有一些特殊形式，否则你几乎不走运。
我会假设你想要的是一个可证明的正确答案，而不是完全避免随机性。
- 运行几轮米勒-拉宾素数测试。如果这失败了，你就知道这个数字是复合的，你就完成了。
- 分解 n-1。为此，最简单的是波拉德的 rho 算法。如果这还不够快，请使用二次筛。
- 检查因子是否为素数，递归使用相同的方法。如果它们是复合的，请继续分解它们。
- 使用卢卡斯素数检验：尝试找到 n-1 阶乘法群模 n 的生成器。选择一个随机数 a，检查 a^(n-1( = 1 (mod n(，以及 a^((n-1(/p( 对于 n-1 的所有素因数 p ≠ 1 (mod n(。如果这是真的，a 是一个生成器，n 是可证明的素数，所以你就完成了。
- 如果 n 是素数，则成功找到生成器的概率为 (1-1/p 1((1-1/p2(...其中p 1， p2， ...是 n-1 的不同素因数。这至少是 1/O(log log n(。因此，在 O(log log n( 尝试之后，您应该成功证明 n 是素数。
- 如果您在证明 n 是素数方面一直失败，请返回步骤 1。也许它毕竟是复合的。