gpt4 book ai didi

c++ - 100% 确定性的快速素数测试?

转载 作者:塔克拉玛干 更新时间:2023-11-03 00:08:04 25 4
gpt4 key购买 nike

我对任意大小的数据类型使用 GMP(带有 MPIR)。我也用了它的素性检验功能,用的是Miller-Rabin方法,但是不准确。这就是我要解决的问题。

我能够通过 sqrt 方法使用蛮力确认数字 18446744073709551253 是素数。

是否有任何方法可以 100% 准确地检查大数是否为素数?

  • 它不应该使用太多的内存/存储空间,几兆字节是可以接受的。

  • 应该比我用的sqrt方法快

  • 它应该适用于大小至少为 64 位或更大的数字。

  • 最后,它应该是 100% 准确的,没有可能!

我有哪些选择?

尽管我可以接受蛮力法(对于 64 位数字),但出于兴趣,我想要更快更大。此外,64 位数字检查速度太慢:总共 43 秒!

最佳答案

对于非常大的数字,AKS primality test是在时间 O(log7.5n log log n) 中运行的确定性素数测试,其中 n 是感兴趣的数量。这比 O(√n) 算法快得多。但是,该算法具有较大的常数因子,因此在您的数字变得相当大之前它并不实用。

希望这对您有所帮助!

关于c++ - 100% 确定性的快速素数测试?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13829229/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com