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 啊!