Leetcode 204.质数计算高级性能

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

翻译一下：
求小于非负整数n个素数数量

解题思路

乍一看是不是很简单，什么边界条件取到根号n就行了，其实它还不是最优的！！！

对于优化的算法，也就是埃拉托色尼筛选法，循环中置对应值的倍数为0，最后统计为1的个数，也就是质数的个数。

发现i*2可以优化成i*i,确实减少了循环次数，例如6,可以由2的倍数置为0，也可以由3的倍数置为0，因此i*i在面对较大的值时效率明显会高于i*2!

### 代码

文文请看下面C++语言的

python

class Solution:
    def countPrimes(self, n: int) -> int:
        '''超时算法，应对大量数据的时候会超时'''
        # 时间复杂度O（n*sqrt(n)）,空间复杂度O（1）
        import math
        nums = 0
        for i in range(2,n):
            if i == 2:
                nums += 1
                continue
            for j in range(2,int(i**0.5)+1):
                if i%j == 0:
                    break
            else:
                print(i)
                nums += 1
        return nums

        '''优化算法'''
        # 时间复杂度O（sqrt(n)）,空间复杂度O（n）
        if n < 3:
            return 0
        results = [1]*n
        results[0],results[1] = 0, 0
        for i in range(2,int(n**0.5)+1):
            if results[i] == 1:
                results[i*2:n:i] = [0]*len(results[i*2:n:i])
        return sum(results)

C++

int countPrimes(int n) {
    int count = 0;
    //初始默认所有数为质数
    vector<bool> signs(n, true);
    for (int i = 2; i < n; i++) {
        if (signs[i]) {
            count++;
            for (int j = i + i; j < n; j += i) {
                //排除不是质数的数
                signs[j] = false;
            }
        }
    }
    return count;
}