楼上抛出的问题很有意思啊。设函数ϕ(x) 等于不大于x的全体质数个数，则时间复杂度可以表示为O(ϕ(⌊√N⌋)) 。因为算法的关键路径：用小于K的所有质数去除N（其中K=⌈√N⌉ ）可通过一个循环体来...
如果不查表的话，
用这种方法判断质数成功后，做标记，也是要比一个个判断效率高很多吧。
PS：用空间换时间后，这个算法效率还会更高。可惜我没楼上这么强的技术水平。只是一个想法
评论
文号 / 867404