问正好有4个除数的数的除数
EN

Stack Overflow用户

提问于 2022-11-05 16:19:40

回答 1查看 97关注 0票数 1

我有一个数n (0

有什么办法能比O(sqrt(n))更快地得到这些除数吗？

采用经典算法求数除数(链接)所需时间为O(sqrt(n))。sqrt(2*10^18)约为10^9，这将花费太多的时间。

另外，一个正好有4个除数的数是两个不同素数的乘积，或者是一个素数的立方体。

发布于 2022-11-05 16:29:34

大O给出了算法的复杂性。它不会给你计算它所需的时间。

如果您的数字是10^18，则O(sqrt(n))算法不需要10^9秒即可完成。它需要10^9次迭代才能完成。

CPU非常快。它们可以每秒执行10^9条指令。

将C#中的18位数600851475143123457与因子3、11和18207620458882529相加，在C++中需要720 11和480 11(非多线程，Ryzen 7 CPU，Release )。请具体说明“会花费太多时间”。您有什么性能要求？

票数 -2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/74329440

复制

相似问题

问正好有4个除数的数的除数EN