V2EX › yanwumo 的所有回复 › 第 1 页 / 共 1 页

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

For Existing Member Sign In

2016 年 12 月 26 日

@ipoh 是的，楼主的失误就在于他写成了代码，问题就变成用 int 实现时间复杂度是怎样了。

2016 年 12 月 26 日

因此，简单的判断质数的方法不能在多项式时间内完成。

2016 年 12 月 26 日

@lxiange 楼主正确
http://softwareengineering.stackexchange.com/questions/197374/what-is-the-time-complexity-of-the-algorithm-to-check-if-a-number-is-prime
判断一个数是否为质数和楼主的问题是相似的。这类问题的区别在于，问题的规模大小与数字本身的大小有关。