【算法】【Python】合数个数（素数筛法）

nums = [True] * 2021  # 创建一个大小为 2021 的布尔数组，假设所有数都是素数
ans = 0  # 统计合数个数

for i in range(2, 2021):  # 遍历 2 到 2020
    if nums[i]:  # 如果 i 是素数
        for j in range(i * i, 2021, i):  # 从 i*i 开始，步长为 i，筛去所有 i 的倍数
            nums[j] = False
    else:
        ans += 1  # 如果 i 已经被标记为 False（说明是合数），计数加 1

print(ans)  # 输出 1 到 2020 的合数个数

这种方法非常高效，我了解这个方法之前还是用的最笨的模拟法：

def count_divisors(n):
    count = 0
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            count += 2 if i != n // i else 1
        if count > 2:
            return True
    return False

res = 0
for i in range(1,2021):
    if count_divisors(i):
        res+=1
print(res)

答案都是1713，虽然在当代计算机中运行这两个Python代码都很快能输出1713，但素数筛还是很好的一种思想。

先初始化全都为True的2021个元素的数组。False代表是合数，True代表默认是素数。

然后从2遍历到2020。如果i是素数，那么i的倍数一定是合数，则全部标记为False，从i*i开始筛选，步长为i。（为什么从 i*i 开始？因为 2i, 3i, …, (i-1)i 之前的倍数已经被更小的数标记过了，无需重复筛选。）

如果i位置已经是False（合数），则ans+=1。