c++如何快速筛素数

素数，又称质数，指除了1和它本身没有其它因数的数

如何用c++判断一个数是不是质数呢？

最原始的算法就是直接枚举

bool isprime(int x){
    if(x <= 1) return 0;
	for(int i=2;i*i<=x;i++)
		if(x%i == 0) return 0;
	return 1;
}

bool isprime(int x){
    if(x <= 1) return 0;
	int k=2;
	while(k*k<=x && x%f!=0) k++;
	if(k*k>x) return 1;
	else return 0;
}

时间复杂度 O(根号n)

bool isPrime(int n){
    if (n <= 1) return 0;
    if (n == 2 || n == 3) return 1;
    if (n % 6 != 5 && n % 6 != 1) return 0;
    for (int i = 5; i < sqrt(n); i+=6){
        //判断是否为奇数,使得算法更高效
        if (n % i == 0 || n % (i + 2) == 0) 
            return 0;
    }
    return 1;
}

如果要筛大量素数，前面的方法速度太慢，怎么办呢

我们可以枚举每一个素数，将其的倍数设为合数，如果从小到大遍历到这个数没被设为合数，那他就是素数

​
    int n,cnt=0;//cnt是素数个数
	int prime[10001];//存素数
	cin >> n;//n表示范围
	memset(prime,1,sizeof(prime);//先全定为素数
	prime[0] = 0;
	prime[1] = 0;//特判
	for(int i=2;i 
当然这种方法会存在许多重复判断，效率会变低，哪还有没有更快的方法呢
 
欧拉筛法 
​
	int n,cnt=0;
	int prime[10001];//存素数
	bool vis[10001];//保证不做素数的倍数
	cin >> n;
	memset(prime,0,sizeof(prime);
	memset(vis,0,sizeof(vis);
	for(int i=2;i<=n;i++){
		if(!vis[i])//不是目前找到的素数的倍数
			prime[cnt++] = i;//找到素数
		for(int j=0;j 
这样效率就大大提高了