数学-计数质数

统计所有小于非负整数 n 的质数的数量。

示例:

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

首先判断2个情况：

比2大的偶数肯定不是质数，因为都能被2整除，排除。
质数的倍数一定不是质数，例如：3 * 2 ，3 * 3，3 * 4，3是质数，那3的任意倍数，都能被3整除，排除。

把上面两个情况全部排除掉后，剩下的就全部都是质数了

复杂度分析

该算法的时间复杂度比较难算，显然时间跟这两个嵌套的 for 循环有关，其操作数应该是：
n/2 + n/3 + n/5 + n/7 + ...
= n × (1/2 + 1/3 + 1/5 + 1/7...)
括号中是素数的倒数。其最终结果是 O(N * loglogN)。
空间复杂度用到了一个标记是否位质数的数组，复杂度为O(N)

func countPrimes(n int) int {
    if n <= 2 {return 0}
    count := 0
    //创建一个数组，用来存储当前数字是否是质数
    isPrimes := make([]bool,n)
    //将数组全部变为true，先假设整个数组都是质数
    for i := 0; i < n; i++{
        isPrimes[i] = true
    }

    for i := 2; i < n; i++ {
        if isPrimes[i]{
        //i的倍数都不是质数，倍数从2倍开始
            for j := i * 2;  j < n; j += i {
             isPrimes[j] = false
            }
        }
    }
    for i := 2; i < n; i++{
        if isPrimes[i]{
          count++
        }
    }
    return count
}

将上面的方法再优化一下，其实不需要循环到n，因为平方之前的计算，在之前的质数计算中，已经被计算了。

i * i
i=2         4,6,8,10,12,14,16.... 
i=3         9,12,15 

2 * i
i=2         4,6,8,10,12,14,16.... 
i=3         6,9,12,15 

其实6是不用计算的，因为i=2 的时候已经计算过了。

因此，我们循环的长度就变成 i * i < n （i < sqrt(n)），也就是时间复杂度降低至O(sqrt(n))
内层和外层同样的逻辑

因此内层的范围也可以直接限制在sqrt(n)

func countPrimes(n int) int {
    if n <= 2 {return 0}
    count := 0
    //创建一个数组，用来存储当前数字是否是质数
    isPrimes := make([]bool,n)
    //将数组全部变为true，先假设整个数组都是质数
    for i := 0; i < n; i++{
        isPrimes[i] = true
    }

    for i := 2; i * i < n; i++ {
        if isPrimes[i]{
        //省去重复的数字判断，直接从i * i 开始计算倍数，因为i * i之前数已经判断过了
            for j := i * i;  j < n; j += i {
             isPrimes[j] = false
            }
        }
    }
    for i := 2; i < n; i++{
        if isPrimes[i]{
          count++
        }
    }
    return count
}

再优化一下，就是省去了两次循环标记数组的操作

func countPrimes(n int) int {
    if n <= 2 {return 0}
    count := n-2
    isPrimes := make([]bool,n)

    for i:=2;i*i<n;i++ {
        if !isPrimes[i]{
            for j := i * i;  j < n; j += i {
                if(!isPrimes[j]){ 
                    //如果当前的数没有被标记过，就将该数标记，同时count的值减1
                    isPrimes[j]=true;
                    count--;
                }
            }
        }
    }
    return count
}