埃拉托斯特尼筛法（Sieve of Eratosthenes）:
1.目的：用于找出一定范围内所有质数的算法
2.基本思想：从小到大逐个筛选数，将合数（非质数）标记掉，最终剩下的即为质数。
3.详细解释：

1>初始化：
创建一个长度为n+1的布尔数组（通常称为isPrime或prime），初始值全部设置为true，表示所有数都是质数。
筛选过程：

2>从2开始，将第一个质数2标记为质数（true），然后将2的所有倍数标记为非质数（false）。
然后找到下一个未被标记的数，即下一个质数3，将其标记为质数，然后将3的所有倍数标记为非质数。
依次类推，直到遍历完所有小于等于n的数。

3>筛选规则：
对于每个质数p，将其所有大于等于p^2且小于等于n的倍数标记为非质数。
这是因为：
1.如果一个数 x 是质数 p 的倍数，并且 x < p p，那么 x 可以表示为 x = p k，其中 k 是一个小于 p 的数。
2.在之前处理质数 k 时，已经标记过 k 的所有倍数，包括 p k。
3.因此，p k 已经在处理 k 时被标记为非质数，而且 k < p，所以 p k < p p。
4.因此，在处理质数 p 时，小于 p p 的 p 的倍数已经被标记过了，不需要再次标记。
eg: i = 2 标记 4 6 8…
i = 3 从9开始 因为 23 = 6 在遍历2的时候就已经遍历了
换言之，一个数的因子，除了根号外 一定一个大一个小，在求倍数的时候，从小的开始遍历，再到大的时候就标记从以这个数作为小因数开始的倍数即可

4>结果提取：
最终留下的isPrime[i]为true的数i即为质数。

4.复杂度：
埃拉托斯特尼筛法的时间复杂度为O(n log log n)，其中n为要筛选的范围内的数的个数。

这种算法的优点在于简单易懂，且在一定范围内找质数的效率很高。然而，对于大范围内的质数筛选，其他更高效的算法可能更合适。

代码：
const int MAX = 1000005;
bool prime[MAX];
void init() {
memset(prime,true,sizeof prime); //知识点
for(int i=2; ii<MAX; i++) { //目的是标记倍数，当以i为小因数开始的倍数以及大于范围时，就没有标记的范围了 换言之，i就是最大的因数
if(prime[i]) {//是素数
for(int j=i2; j<MAX; j+=i)//从2倍开始，n倍
prime[j]=false;//各个倍数
}
}
}

解释：为什么i*i<MAX;
在埃拉托斯特尼筛法中，当我们处理质数 p 时，我们只需要标记 p 的倍数，其中 p 的平方小于或等于 n。这是因为如果 p 的平方大于 n，那么 p 的倍数已经超出了我们要筛选的范围，不需要再标记这些倍数。

举个例子：

假设我们要找出小于等于 30 的所有质数：

当处理质数 2 时，我们从 2 的平方开始标记倍数，即从 4 开始。因为 2 的平方是 4，小于等于 30，所以我们需要标记 2 的倍数。
当处理质数 3 时，我们从 3 的平方开始标记倍数，即从 9 开始。因为 3 的平方是 9，小于等于 30，所以我们需要标记 3 的倍数。
当处理质数 5 时，我们从 5 的平方开始标记倍数，即从 25 开始。因为 5 的平方是 25，小于等于 30，所以我们需要标记 5 的倍数。
如果我们考虑一个更大的质数，比如 7，7 的平方是 49，大于 30，这意味着 7 的倍数已经超出了我们要筛选的范围，因此不需要再标记 7 的倍数。
因此，为了确保我们在筛选范围内正确地标记质数的倍数，我们需要保证 p 的平方小于或等于我们要筛选的最大值 n。

知识点：
一.memset()函数
1.作用：用于将一块内存空间的每个字节都设置为指定的值
2.用法：memset(初始地址,要设的值,类型长度) eg:memset(prime,true,sizeof prime);

注意点：在C++中，memset函数经常用来初始化整型数组、字符数组或其他基本数据类型的数组。但对于非整型数据类型，如bool类型，使用memset可能会导致一些问题，因为bool类型在C++中并不是一个字节大小的数据类型，而是一个字节中的某一位。因此，对于bool类型数组，最好使用循环或其他方法显式地设置每个元素的值。
3.头文件：

扩展：std::fill 函数
1.作用：是 C++ 标准库中的一个函数模板，它用于将指定的值赋给一个容器或数组的特定范围内的所有元素
2.头文件：
3.用法：
eg:vector vec(5);
fill(vec.begin(), vec.end(), -1); // 将 vector 中的每个元素都设置为 -1

fill()函数和memset()函数的区别
1.std::fill
是 C++ 标准库中的一个模板函数，定义在 头文件中。
可以用于任何类型的容器，包括数组、std::vector、std::list、std::array 等。
可以填充任何类型的值，不仅仅是字节值。
需要两个迭代器参数来指定要填充的元素范围。
安全性更高，因为它基于类型，编译器会检查类型匹配，减少类型错误的风险。
2.memset
是 C 语言标准库中的一个函数，定义在 头文件中。
通常用于填充字节序列，适用于简单的数据类型（如 char、unsigned char 等）。
不能用于填充复杂数据类型，因为它只处理字节级别的赋值。
只需要一个指针参数指向要填充的内存块的开始位置，以及要设置的值和要填充的字节数。
效率可能更高，因为它直接操作内存，不涉及迭代器的解引用和递增操作。

二.i++和++i的区别
++i：返回 i 增加 1 后的值
i++：返回 i 增加 1 之前的值
eg:
i = 1;
int a = ++i; // i 现在是 2，a 是 2

i = 1;
int b = i++; // i 现在是 2，但 b 是 1