# 质数

质数又叫素数，是指在大于 1 的自然数中，除了 1 和它本身以外不在有其它因数的自然数。2 是最小的质数。

因数是指整数 a 除以整数 b (b≠0) 的商正好是整数而没有余数，我们就说 b 是 a 的因数。

# 判断一个数 n 是否是质数

明确概念之后，接下来的问题是如何判定某个数是否是质数呢？

一个标准的方式是使用试除法。

# 试除法

用 n 除以 2 到 $\sqrt{n}$ 的所有整数，若其中没有可以整除的，则可以认定 n 是一个质数。

这里有一个问题是为什么试除法判断到 $\sqrt{n}$ 就可以，而无需除到 n 本身呢？

这是因为自然数的因数都是成对出现的。比如：12 的因数有 2 和 6，3 和 4。

既如此，我们只需要枚举较小的那个因数即可，而较小因数中的最大那个也不会超过$\sqrt{n}$ 。

证明：
假设较小的因数为 d ，那么较大的因数则为 ${ {n} \div{d} }$, 公式表示为 ${ {d}\le{n}\div{d} }$，进而推出 ${ {d}^2\le{n} }$，最终得到结论 ${ {d} \le \sqrt{n} }$。

# Code

参考题目: AcWing 866. 试除法判定质数

def is_prime(n):

    if n < 2:

        return False

    i = 2

    while i <= n // i:

        if n % i == 0:

            return False

        i += 1

    return True

n = int(input())

for _ in range(n):

    print('Yes' if is_prime(int(input())) else 'No')

# 分解质因数

给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

比如：将数字 12 分解成质因数就是 2*2*3 ，那么其中共有两个质因数，分别是 2 和 3。其中 2 的指数是 2，3 的指数是 1。即 12 分解质因数后结果为${2^2 * 3^1}$。

# 分解质因数方法

那么如何分解质因数呢？先要理解如下性质：

1. n 的质因子只能有一个大于 ${\sqrt{ n } }$ 的数。因为如果存在两个大于 ${ \sqrt{ n } }$ 的数，这两个数的乘积一定会大于 n。
2. 每个正整数都能以唯一的方式表示成它的质因数乘积。换言之，对于每个正整数来说，它的质因数乘积的结果是唯一的。

明确上面两个性质，不难理解分解质因数需要如下步骤：

1. 枚举 2 到 ${ \sqrt{n} }$ 为 i 。
2. 用 n 去除以 i 判断余数，则有两种情况。
3. 如果余数为 0，说明 i 是 n 的质因子之一。
4. 用 cnt 表示当前质因子 i 的指数，则有如下伪代码：

while ((n % i) == 0){

    cnt ++;

    n /= i

}

伪代码对应的作用是求出当前质因数 i 的个数。比如当前 n 是 12，当前 i 是 2，则一轮循环过后 n 变成 6，下一轮循环 6 又能提供一个质因数 2。如此，最终将 n 分解成为最小的质因数。

# Code

参考题目: AcWing 867. 分解质因数

def find(x):

    i = 2 

    while i <= x // i:

        # 如果 i 是质因子则判断个数

        if x % i == 0:

            cnt = 0

            while x % i == 0:

                cnt += 1

                x //= i

            print(f'{i} {cnt}')

        i += 1

    if x > 1:

        print(f'{x} 1')

    print('')

n = int(input())

for _ in range(n):

    find(int(input()))

# 筛质数

参考题目: AcWing 868. 筛质数

给定一个正整数 n，请你求出 1∼n 中质数的个数。

例如：此时 n 为 12，那么需要判断的就是 1~12 中所有的质数。（下面例子中，如无特殊说明，n 也是 12。）

# 1. 普通的翻倍筛选

普通的翻倍筛法非常简单。

翻倍筛法的做法是，从最小的质数 2 枚举到 n，依次判断是否是质数。在枚举的同时把枚举到的数翻倍，翻倍后得到的数一定不是质数（原因参考质数定义），因此可以直接筛掉。

比如：当前枚举到了 2，持续将 2 翻倍就可以筛选掉 4,6,8,10,12 ；接下来枚举到了 3，持续将 3 翻倍就可以筛掉 6,9,12 。以此类推直到枚举完成，就选出了所有的素数。

# Code

从代码循环次数中可以看出，这种做法的时间复杂度是${O(nlogn)}$ 。

n = int(input())

N = 1000010

st = [0] * N # 标记是不是质数

p = [0] * N # 质数数组

def get_primes(n):

    cnt = 0 # 质数数组下标 同时统计个数

    for i in range(2, n + 1):

        if not st[i]: # 判断是否是质数

            p[cnt] = i

            cnt += 1

        j = i + i # 翻倍筛选

        while j <= n: # 循环结束

            st[j] = 1

            j += i

    return cnt

# 2. 埃氏筛

之所以叫埃氏筛，是因为这种筛质数的方式是一个叫 埃拉托斯特尼 的希腊数学家提出的。

仔细观察普通筛法的操作，无论质数还是合数都用来做了翻倍筛选。也就是当枚举到 4 的时候，将 4 翻倍筛掉 8 和 12 ，可是在枚举 2 的时候 8 和 12 已经被筛掉了，也就是做了冗余的工作。

埃氏筛就是去掉了这部分冗余工作，也就是说合数不再用来筛选，转而只使用质数筛选。

# Code

在代码上的体现就是把普通筛法中的用于筛选的循环放到只有枚举到质数的时候才执行。

这种方法的时间复杂度是${O(nlog{logn})}$ ，这个复杂度其实已经无限接近${O(n)}$ 。

def get_primes(n):

    cnt = 0

    for i in range(2, n + 1):

        if not st[i]:

            p[cnt] = i

            cnt += 1

            # 下面循环是翻倍筛选

            j = i + i

            while j <= n:

                st[j] = 1

                j += i

    return cnt

# 线性筛

尽管埃氏筛的复杂度已经足够小，但是还不是真正的线性算法。还有一种真正${O(n)}$ 时间复杂度的筛法，称为线性筛。

线性筛的操作非常之巧妙，在了解线性筛之前，我们先看一下埃氏筛是否存在冗余操作。

按照埃氏筛的逻辑，只用质数翻倍筛选。那么，当枚举到 2 的时候，会进行翻倍筛选， 10 会被筛掉；继续枚举当枚举到 5 的时候，我们知道 5 也是质数，那么 5 进行翻倍筛选，又筛掉了一遍 10 ，这也就是埃氏筛的冗余操作。

线性筛就是解决了埃氏筛的这一部分冗余操作，即每个合数只会被它的最小的质因子筛掉。

这样， 10 的最小质因子是 2 ，那么它只会被 2 筛掉，而不会遇到 5 再被筛一次。

# Code

def get_primes(n):

    cnt = 0

    for i in range(2, n + 1):

        if not st[i]:

            p[cnt] = i

            cnt += 1

        # 循环 2

        j = 0

        while p[j] <= n // i:

            st[p[j] * i] = 1

            # 结束条件

            if i % p[j] == 0:

                break

            j += 1

    return cnt

线性筛从代码中标记的 循环2 的部分开始与前面两种筛法出现明显不同。

循环2 的循环条件是 p[j]<=n//i ，变形一下就是 p[j]*i<=n ，与上面两种筛法的循环条件就比较类似了。而 p[j]*i 正是每次筛选掉的合数。

而循环结束条件 i%p[j]==0 正是线性筛最精妙的部分。可以从两方面理解这一条件的含义。理解的基础是要始终明确一个概念，那就是 p 数组中的质数是递增的 (2,3,5...) 。

1. 那么，当 i 遇到第一个能整除的 pj 时， pj 一定是 i 的最小质因子，所以， pj 也一定是 pj*i 的最小质因子。

   比如， i 为 9 ， pj 为 3 。此时， pj 是 i 的最小质因子，那么 pj 也一定是 pj*i=27 的最小质因子。

2. 当 i 无法整除 pj 时，也就是 i%pj!=0 ，一定有 pj 小于 i 的最小质因子，也就是小于 i 的所有质因子，那么 pj 还是 pj*i 的最小质因子。

   比如， i 为 7 ， pj 为 3 。此时，pj 一定是 pj*i=21 的最小质因子。

试想一下，没有这个循环结束条件会发生什么？

在 n=12 的例子中， 没有结束条件 ，则出现如下状况：

1. i 为 4 时候，p 为 [2,3] ， pj 为 2 ， pj*i 筛掉 8 ；
2. 执行 j+1 后， pj 变成 3 ；
3. pj*i 筛掉 12 ；
4. 继续枚举，当 i 为 6 ， pj 为 2 的时候，满足循环条件，于是又筛掉一遍 12 ；

于是我们惊奇的发现， 12 这个数字被重复筛掉，与线性筛的基本原则 (每个合数只被它的最小质因子筛掉) 不符。

综上，这个精妙的结束条件，才是线性筛中最重要的部分。

# 总结

本文粗略的描述了质数及一些与之相关的概念。并解决了三个问题。分别是:

1. 判断一个数是否是质数；
2. 分解质因数；
3. 判断出 1~n 中有多少质数；

END