[算法练习笔记] 5、筛质数 + 前缀和解决 非素数个数问题

一、筛质数算法

名词解释：

质数： 只有1和它本身两个因数（约数），那么这样的数叫做质数，也叫素数。

合数： 除了能被1和它本身整除，还能被其他的正整数整除，那么这样的数叫做合数。

筛质数： 将筛选范围内的质数全部筛选出来

待查区间：1 ~ n

筛选方法如下：

1、最简单筛质数法

也就是枚举从2 ~ n的所有数，一个个来判断是否为质数。

时间复杂度约为O(n²)，最劣。

关键代码

for(int i=1;i