质数 or 素数

质数的判定——试除法 分解质因数——试除法1-num范围内的质数——筛质数朴素筛法埃氏筛法线性筛法（欧拉筛）
在大于1的整数中，如果只包含 1 和本身这两个约数，则称为质数。

质数的判定——试除法

这里因为 约数 肯定是成对出现的，所以只需要判断较小的约数就好了，那最小的素数 最大为 sqrt(num) , 所以只需要判断到 sqrt(num)（是需要包含 sqrt(num）的)就好了。
然后其实每次都计算 sqrt(num) 都比较复杂，所以不推荐。而是推荐 while i ≤ n // i: i += 1
# 不推荐
def is_prime(num):
		if num <= 1:
				return False
		for i in range(2, sqrt(num)+1):
				if num % i == 0:
						return False
		return True

# 推荐 ！！  时间复杂度 \sqrt(n)
def is_prime(num):
		if num <= 1:
				return False
		i = 2
		while i <= n // i:
				if num % i == 0:
						return False
				i += 1

		return True

分解质因数——试除法

数字 num 可以分解为几个质数相乘的形式，如30=2×3×5
， 即 个 相乘 ， 个 相乘，，这些底数均为质数！
思路
从小到大，枚举n的所有因数。
代码看起来是遍历了所有的数字，但其实是只由质数 才会满足 if num % i == 0
假设 num=12, 那么在i= 2的时候，就会把 2 通过while循环一直除，得到 2 个 2相乘，且此时num 已经等于了3，所以在i=4的时候已经没 4 什么事情了，别的同理。因为大的合数一定是由小的质数相乘得到。比如4 一定是由 2 * 2 得到 ，6 一定是由 2 * 3 得到。
所以 i 为合数时，不会进入if , 更不会进入while循环。
def divid(num):
    # 从小到大枚举所有的数字，
    # 因为 i 是从小到大的，所以当分解到 i 时候，
    # 就意味着把 2 到 i-1 之间的所有质因子除干净了
    for i in range(2, num+1, 1):
        # num 是 i 的倍数 ，并且 num中不包含任何 2到i-1之间的质因子
        # 且 i 中也不包含任何 2到i-1之间的质因子
        # 因此此时 i 一定是质数
        if num % i == 0:
						# 此处表示有 s 个 i 相乘
						# i 为底数， i 一定是质数
						# 因为大的合数一定是由小的质数相乘得到的
						# 再遍历到小的质数时，就通过这个 while 循环把大的质数给消灭了
            s = 0
            while num % i == 0:
                num //= i
                s += 1
            print(f"{s}个{i}相乘")


# 开始优化
# n 中只包含一个 大于等于 sqrt(n)的质因子, 反证法，要是超过两个，相乘就大于 n 了
# 所以可以之查找小于等于 sqrt(num) 之间的质因子，
# # 最后 num 如果大于 1 ,那么这个 num 就是 这个大于等于 sqrt(num)的质因子

import math
def divid(num):
		# 这里把搜索空间缩减到了 sqrt(num)
    i = 2
		while i <= num // i:
        if num % i == 0:
            s = 0
            while num % i == 0:
                num //= i
                s += 1
            print(f"{s}个{i}相乘")
				i += 1
		# 
    if num > 1:
        print(f"1个{num}相乘")

>>>divid(16)
4 个 2 相乘
>>>divid(20)
2个2相乘
1个5相乘
时间复杂度不一定一直是 sqrt(num)， 最好的是log num，即如果num是2 的n次，或者3 的n次等情况时，直接一次就会被除干净。

1-num范围内的质数——筛质数

给定一个正整数num，求出 1-num 中的质数
思路
写出 2- num中的所有数，然后先把2的所有倍数删掉，再把3的所有倍数删掉，依次往后删除。。
那么剩下的数字就是质数。
证明，对于 没被删掉的数字 p, 那么 p 就不是 从 2 到 p-1 中的任意一个数字的倍数，所以 p 就是质数。

朴素筛法

def get_primes(num):
    # 返回 [2,num]之间的所有质数

    # 标记每个值是否应该被移除
    st = [False for _ in range(num+1)]
    # 存放最后的素数
    primes = []
    
    for i in range(2, num+1):
        # 如果当前数字没有被标记为移除状态，那么他就是质数
        if st[i] is False:
            primes.append(i)

        # 把 i 的所有倍数都标记为 移除状态
        j = i + i 
        while j <= num:
            st[j] = True
            j += i

    return primes
复杂度分析
当 i = 2 时，while 循环执行 n/2 次，当i = 3 时， while 循环 执行 n / 3 次，依次类推，有：

埃氏筛法

其实并不需要用for循环把所有数字都判断一边，比如8就没必要判断，因为前面判断 2 的时候同时把8的倍数移除过了，9也没必要判断，因为前面判断3的时候都移除过了。所以只需要判断质数即可，即只移除质数的倍数
我们把2~n的数按顺序写出来：
notion imagenotion image
从前往后看，找到第一个未被划掉的数，2，这说明它是质数。然后把2的倍数（不包括2）划掉：
notion imagenotion image
下一个未被划掉的数是3，它是质数，把3的倍数划掉：
notion imagenotion image
接下来应该是5，但是5已经超过  了，所以遍历结束，剩下未被划掉的都是素数：
notion imagenotion image
import math

def get_primes(num):
    st = [True for _ in range(num+1)]
    primes = []
    
    for i in range(2, num+1):
        # 如果当前数字没有被标记为移除状态，那么他就是质数
        if st[i] is True:
            primes.append(i)

            # 把质数 i 的所有倍数都标记为 移除状态
            j = i + i 
            while j <= num:
                st[j] = False
                j += i

    return primes
上述代码还可以进一步优化。在试除法判断数字是否为素数时，我们使用了从1到 \sqrt n 的for循环来遍历数字，此处依旧可以采用此技巧，但是需要注意，保存素数的逻辑应该是先保存所以数字然后移除掉非素数。dai如下：
import math

def get_primes(num):
    st = [True for _ in range(num+1)]
    primes = set([i for i in range(2, num+1)])
    
    for i in range(2, math.sqrt(num)):
        # 如果当前数字没有被标记为移除状态，那么他就是质数
        if st[i] is True:
            # primes.append(i)

            # 把质数 i 的所有倍数都标记为 移除状态
            j = i + i 
            while j <= num:
                st[j] = False
								primes.remove(j)
                j += i

    return primes
时间复杂度分析
其操作数应该是：n/2 + n/3 + n/5 + n/7 + …= n × (1/2 + 1/3 + 1/5 + 1/7…)。括号中是素数的倒数和，其最终结果是 O(N * loglogN)
定理 之间有 个质数
原本要计算 之间的个数，现在只需要计算 , 即时间复杂度缩减了 倍。原先时间复杂度为 ,现在时间复杂度约等于为 ，真实的时间复杂度为

线性筛法（欧拉筛）

思想：每一个数 n 只会被它的最小质因子筛掉。
过程：从头到尾遍历，第一个数是2，未被划掉，把它放进质数表：
notion imagenotion image
然后我们用 2 去乘质数表里的每个数，划掉它们：
notion imagenotion image
下一个是3，加入质数表，划掉6、9：
notion imagenotion image
下一个是4（注意这里划掉的数也要遍历，只是不加入质数表），先划掉 8，但我们不划掉12，因为12  应该由它的最小质因数2筛掉，而不是3。
notion imagenotion image
实际上，对于 x ，我们遍历到质数表中的 p ，且发现  p|x 时，就应当停止遍历质数表。因为：设 x = pr(r ≥ p) (p 本身是 x 的最小质因数），那么对于任意 p’ > p, 有 p’x = p p’r = p(p’r) ，说明 p’x 的最小质因数不是 p’, 我们不应该在此划掉它。比如 x = 10 时，遍历质数表中的p，当p=2 时，就应该停止遍历，因为后面的质数比如3 * 10 的最小质数是2 而不是 3，我们应该在 x = 15 的时候，再将 15 * 2 筛掉。
在 while 循环里面，有如下两种情况
  • 当 if 发生时， 一定是 的最小质因子，因为 是从小到大的；所以 也一定是 的最小质因子
  • 当 if 不发生时， 一定是小于 的所有质因子，所以 也一定是 的最小质因子
所以 st[primes[j] * i] = True 执行的时候，一定有 为 的最小质因子。
就是说移除的每一个数字，都一定是用它的最小质因子删除的。每一个数字都只有一个最小质因子，所以每个数只会被删除一次，所以是线性的。
思路
import math

def get_primes(num):
    # 返回 [2,num]之间的所有质数

    # 标记每个值是否应该被移除
    st = [True for _ in range(num+1)]
    
    primes = []
    
    for i in range(2, num+1):
        if st[i] is True:
            primes.append(i)

        j = 0
				# 枚举当前所有的质数，质数的 i 倍一定是合数
        while primes[j] * i <= num:
            st[primes[j] * i] = False
            if i % primes[j] == 0:
                break
            j += 1

    return primes
def get_primes(num):
    st = [True for _ in range(num +1)]
    primes = []

    for i in range(2, num+1):
        if st[i] :
            primes.append(i)
        # 遍历当前所有的质数，质数的 i 倍 也一定不是质数！
        for j in primes:
            # 超过范围了，就不用判断了
            if j * j >= num:
                break
            # 质数 j 的 i 倍 一定不是质数了, 
            st[j * i] = False
            # 如果 i % j== 0 那么说明 i*j 的 最小质因子就是 j, 
						# 且 i 是 j 的整数倍，没必要继续判断下下去了
            # 为了保证被筛数 i*j 的最小因子为 j,
            if i % j == 0:
                break
🔇
172. 阶乘后的零