C++欧拉筛

欧拉筛的基本概念

欧拉筛（Euler Sieve）是一种用来筛选素数的算法。与传统的埃拉托斯特尼筛法（Eratosthenes Sieve）相比，欧拉筛能更快地筛选出一定范围内的素数，因为它避免了不必要的筛选操作，提高了效率。

欧拉筛的工作原理

欧拉筛的核心思想是保证在2到n范围内，每个合数都能被唯一地分解为其最小质因数与除自己外最大的因数相乘的形式。这意味着对于每个数n，我们只使用n中除n之外最大的因数来筛掉合数。例如，对于合数45（45=335），我们确保使用15（即3*5）来筛掉45，而不是更小的质数。这样可以保证每个合数只被筛一次，从而降低总的筛选次数，提高效率。

欧拉筛的C++实现

在C++中，欧拉筛可以通过以下代码实现：

#include<bits/stdc++.h>
using namespace std;
vector<int> Prime;
bool isPrime[10010]={1,1};
 
int main(){
	for(int i=2;i<=100;i++){
		if(isPrime[i]==0) Prime.push_back(i);
		for(int j=0;j<Prime.size()&&Prime[j]*i<=100;j++){
			isPrime[i*Prime[j]]=1;
			if(i%Prime[j]==0) break;
		}
	}
	for(int i=0;i<Prime.size();i++) cout<<Prime[i]<<" ";
	return 0;
} 

这段代码首先创建了一个布尔数组，其中每个元素默认值为true，表示对应的数是素数。然后，通过循环从2开始遍历每个数，如果该数是素数，则将其加入素数列表，并更新数组，将所有该数的倍数标记为非素数。最后，打印出所有的素数。

注意事项

在使用欧拉筛时，需要注意避免对素数列表进行不必要的操作，如重复添加相同的素数，或者在不需要的地方修改数组。此外，为了提高效率，应该尽可能地减少对数组的访问，只在必要时才更新它。