本文共 1703 字，大约阅读时间需要 5 分钟。

对普通版求素数的

bool isPrime(int n){	int end = sqrt(n);	if(n == 1 || n == 0)		return false;	if(n == 2)		return true;		if(n%2 == 0)		return false;//			for(int i = 3; i*i <= n+1; i+=2){这里必须是n+1不然是错的//				if(n%i == 0)//					return false;//			}	for(int i = 3; i <= end; i+=2){//这里就可以直接是开根号的		if(n%i == 0)			return false;	}	return true;}

筛法求素数（O（nloglogn））

#include
   
    #include
    
     using namespace std;int a[100];int vis[100];int prime[100];int n; void getPrime(){	int prime;	int ans;		for(int i = 2; i <= n; ++i){//数组模拟			ans = prime = i;			if(prime*prime > n) break;			while(ans < n){				ans += prime;				a[ans] = 0;			}		}		for(int i = 2; i <= n; ++i){			if(a[i] != 0){				cout << a[i] <<" ";			}		}}void getPrimeSec(){	int cnt = 0;	memset(vis,0,sizeof(vis));	for(int i = 2; i <= n; ++i){		if(!vis[i]){			prime[cnt++] = i;			for(int j = i*i; j <= n; j += i){//从 i*i开始 				vis[j] = 1;			}		}	}	for(int i = 0; i < cnt; ++i){		cout << prime[i] <<" ";	}}int main()	{		cin >> n;		for(int i = 0; i <= n; ++i){			a[i] = i;		}		a[0] = a[1] = 0;		getPrime();		cout <
    
   

欧拉线性筛法

void eulerPrime(int n){	int cnt = 0;	memset(vis,0,sizeof(vis));		for(int i = 2; i < n; ++i){		if(!vis[i])//注意和前面的prime位置区别			prime[cnt++] = i;		for(int j = 0; j < cnt && i*prime[j] < n; ++j){			vis[i*prime[j]] = 1;			if(i%prime[j] == 0)				break;		}	}	for(int i = 0; i < cnt; ++i){		cout << prime[i] <<" ";	}}

然后利用了每个合数必有一个最小素因子，每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。

代码中体现在： if(i%prime[j]==0)break; prime数组 中的素数是递增的,当 i 能整除 prime[j]，那么 i*prime[j+1] 这个合数肯定被 prime[j] 乘以某个数筛掉。

也就是此后I*prime[j+1]会被 prime[j]筛掉 如果循环不终止则 会重复筛除

因为i中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素数同理。所以不用筛下去了。 在满足i%prme[j]==0这个条件之前以及第一次满足改条件时,prime[j]必定是prime[j]*i的最小因子。

转载地址：http://umimi.baihongyu.com/