筛法求素数

素数总是一个比较常涉及到的内容,掌握求素数的方法是一项基本功。

基本原则就是题目如果只需要判断少量数字是否为素数,直接枚举因子2 。。N^(0.5) ,看看能否整除N。

如果需要判断的次数较多,则用下面介绍的办法预处理。

void make_prime()  {      
	memset(prime, 1, sizeof(prime));
	prime[0]=false;     
	prime[1]=false;     
	int N=31700;      
	for (int i=2;  i<N;  i++)         
	  if (prime[i]) {          
		primes[++cnt ]=i;     
		for (int k=i*i; k<N; k+=i)        
			prime[k]=false;       
	  }      
	return;
}   

初始时,假设全部都是素数,当找到一个素数时,显然这个素数乘上另外一个数之后都是合数(注意上面的 i*i , 比 i*2 要快点 ),把这些合数都筛掉,即算法名字的由来。

0 条评论
发表一条评论