零、写在前面

  这是《算法零基础100讲》 专栏打卡学习的第八天了。
  有不少同学已经不甘心只刷题了，「 解题报告 」 也已经陆续安排上了。每天都会有五六篇高质量的 「 解题报告 」 被我 「 加精 」。如果觉得自己有能力的，也可以来 「 万人千题 」 社区发布你的 「 解题报告 」。千万级流量，你我共同拥有，当然，不忘初心才是最重要滴。
  上一节简单学习了一些数论的概念，并且知道的素数的判定方法，那么今天我们来看如何对一个范围内的数进行素数判定操作。

一、概念定义

1、素数筛选

  首先 1 不是素数，如果 $n>1$，则枚举 $[1，\sqrt n]$ 范围内的素数进行试除，如果至少有一个素数能够整除 $n$，则表明 $n$ 是合数，否则是素数。
   $[1，\sqrt n]$ 范围内的素数可以通过筛选法预先筛出来，用一个数组 f[i]标记 $i$ 是素数与否，筛选法有很多，这里介绍一种最常用的筛选法——Eratosthenes筛选法。

2、Eratosthenes筛选法

  用一个标记数组 $f[maxn]$ ，其中 $f[i] = 0$ 代表 $i$ 为素数，否则为非素数。首先，因为 $0$ 和 $1$ 都不是素数，所以，标记 $f[0] = f[1] = 1$。
  1）从未被标记的数中找到最小的数，为 2，它不是任何（1 或者 它本身）数的倍数，所以 2 是素数，并且这时候，我们将 4、6、8、10、… 等 2 的倍数的 $f[i]$ 都标记为 1；
  2）从未被标记的数中找到最小的数，3，它也是素数，这时候，我们将 6、9、12、… 等 3 的倍数的 $f[i]$ 都标记为 1；
  3）从未被标记的数中找到最小的数，5，它也是素数，这时候，我们将 10、15、20、… 等 5 的倍数的 $f[i]$ 都标记为 1；
  4）从未被标记的数中找到最小的数，7，它也是素数，这时候，我们将 14、21、28、… 等 7 的倍数的 $f[i]$ 都标记为 1；
   $i$）……
  通过这种方式，遍历完标记数组，如果没有被标记为 1 的数，就是素数了。

3、欧拉筛法

  此为扩展进阶内容，将在 《算法进阶100讲》（可联系作者了解详情） 中进行讲解。

二、题目描述

  统计所有小于非负整数 $n(0 \le n \le 5 \times 10^6)$ 的素数的数量。

三、算法详解

  在筛选法中，将 $i$ 的倍数都标记为合数，由于 $i*2、i*3、i*(i-1)$在 $[1, i)$ 的筛选过程中必定已经被标记为合数了，所以 $i$ 的倍数只需要从 $i*i$ 开始即可，避免不必要的时间开销。需要注意 $i*i$ 超出整型后变成负数的问题，所以转化成 long long。
  虽然筛选算法有两个嵌套的轮询，但是第二个轮询只有在 $i$ 是素数的时候才会执行，而且随着 $i$ 的增大，它的倍数会越来越少，所以整个算法的时间复杂度并不是 $O(n^2)$，而且远远小于 $O(n^2)$。
  可以在内层循环f[i] = 1进行赋值前加入一个计数器 $count$，计数器的值就是该程序的总执行次数，对 $maxp$ 进行不同的值测试发现 $int(count / maxp)$ 的值随着 $maxp$ 的增长变化非常小，总是维持在 2 左右，所以这个算法的复杂度可以近似看成 是 $O(n)$，更加确切的可以说是 $O(nC)$，其中 $C$ 为常数， $C$ 一般取 2 )。
  事实上，实际应用中由于空间的限制（空间复杂度为 $O(n)$）， $maxp$ 的值并不会取的很大， $10^7$ 基本已经算是极限了，再大的素数测试就需要用到 拉宾-米勒 ( $Rabin-Miller$) 大数判素了。

四、源码剖析

#define maxn 5000001                             // (1)
#define ll long long                             // (2)

bool f[maxn];                                    // (3)

int countPrimes(int n){
    int i;
    int cnt = 0;                                 // (4) 
    ll j;                                       
    f[0] = f[1] = 1;                             // (5)
    for(i = 2; i < n; ++i) {
        if(!f[i]) {
            ++cnt;                               // (6)
            for(j = (ll)i * i; j < n; j += i) {  // (7)
                f[j] = 1;                        // (8)
            }
        }
    }
    return cnt;
}

• $(1)$ 标记数组的上限；
• $(2)$ 可以理解成ll是 64位整型long long的缩写；
• $(3)$ 定义标记数组f[]；
• $(4)$ cnt用于对素数进行计数；
• $(5)$ 0 和 1 都不是素数，所以都标记为 1；
• $(6)$ 遇到一个素数，cnt就进行一次自增；
• $(7)$ 由于 $i*2、i*3、i*(i-1)$在 $[1, i)$ 的筛选过程中必定已经被标记为合数了，所以 $i$ 的倍数只需要从 $i*i$ 开始即可，避免不必要的时间开销。需要注意 $i*i$ 超出整型后变成负数的问题，所以转化成 long long；
• $(8)$ 将所有 $i$ 的倍数标记为合数；

五、推荐专栏

六、习题练习

请参考原文