204. Count Primes

Description:

Count the number of prime numbers less than a non-negative number,n.

这个题看起来很简单, 的确很简单, 但是一半都要O(n 2or1.5)的时间复杂度。

巧妙地方式又来了。 

如果一个数a是素数,那么a*a 一定不是素数 a*a+a 也一定不是素数。 那我们可以先假定多有点数都是素数, 从2开始扫描知道一个数的平方<n , 为什么是平方小于n而不是本身呢, 很简单, 因为我们接下来要判断的值以一个数的平方开始。

优雅的代码又来了, Elegant 啊!

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容