几种常见的素数筛选法

几种常见的素数筛选法 2022-12-02 723

素数筛选在很多题目上都会出现，这里对一些方法做一些总结第一种教科书里面的方法，对于数字n枚举小于等于 s q r t ( n ) sqrt(n) sqrt(n)的所有数字，如果n能够整除其中一个，就能判断n不是素数，时间复杂度大致是（ n ∗ l o g n n*logn n∗logn) 当然由于偶数中只有2是素数，所以在筛选时可以从3开始，写循环时递增2，进一步节省时间

bool isprime(int n)
 {
          
   
 	int t;
 	for(t=2;t<=sqrt(n);t++){
          
   
 		if(!n%t){
          
   
 			return false;
 		}
 	}
 	return true;
 }

下面证明一下为什么到 s q r t ( n ) sqrt(n) sqrt(n)就能判断是n是否是素数 : 假设 n = s q r t ( n ) ∗ s q r t ( n ) = n 1 ∗ n 2 n = sqrt(n) * sqrt(n) = n1 * n2 n=sqrt(n)∗sqrt(n)=n1∗n2 ，且 s q r t ( n ) sqrt(n) sqrt(n) 是整数 n1 和 n2 必有一个小于 s q r t ( n ) sqrt(n) sqrt(n)，一个大于，所以到 s q r t ( n ) sqrt(n) sqrt(n)就能判断n是否为素数

第二种（埃氏筛选法）这是一种历史悠久的算法了，时间复杂度大致是 n ∗ l g l g n n*lglgn n∗lglgn，具体的做法是是，把素数的n倍标记为false最后为true的数就是素数

int isprime[n+1];
cnt = 0;
bool prime[n+1];
for(int t=1;t<=n;t++){
          
   
	prime[t]=true;
}
prime[0]=prime[1]=false;

for(int t=2;t<=n;t++){
          
   
	if(prime[t]){
          
   
		isprime[cnt++]=t;
		for(int i=2;i*t<=n;i++){
          
   
			prime[i*t]=false;
		}
	}
}

因为每个合数都能被分解为若干个素数的乘积，所以我能可以保证每个合数都会被筛选到，但是这个算法也有缺陷，有的合数会被筛选两次，造成时间上的浪费，比如6：会被 2 ∗ 3 2*3 2∗3筛选一次，同时也会被 3 ∗ 2 3*2 3∗2筛选一次

第三种（线性筛也叫欧拉筛）我看了好久的代码都不懂，只能大概的了解

代码引用于https://blog..net/Dinosoft/article/details/5829550

#include<iostream>
using namespace std;    
const long N = 20;   
long prime[N] = {
          
   0},num_prime = 0;    
int isNotPrime[N] = {
          
   1, 1};   
int main()    
{
          
     
    for(long i = 2 ; i < N ; i ++)       
    {
          
               
		if(! isNotPrime[i])               
	 		prime[num_prime ++]=i;  
		//关键处1        
		for(long j = 0 ; j < num_prime && i * prime[j] <  N ; j ++)
    		{
          
                  
		      	isNotPrime[i * prime[j]] = 1;  
	  		if( !(i % prime[j] ) )  //关键处2                  
				break;           
		}        
	} 
	
	for(int t=0;t<num_prime;t++){
          
   
		cout<<prime[t]<< ;
	}       
	return 0;   
}

这个筛选主要分为两种一种是 i是素数，那么当prime[j]==i时就会跳出循环，这个过程本质上是一个大的素数乘以一个小于等于它的素数，接下来这个素数只会增加所以不会出现如 15 = 3 ∗ 5 15 = 3 * 5 15=3∗5，分别被 3 ∗ 5 3 * 5 3∗5筛一次， 5 ∗ 3 5 * 3 5∗3筛选一次的情况，因为 3 ∗ 3 3 *3 3∗3时就停止了，只会被 5 ∗ 3 5*3 5∗3筛选到当 i 是合数时，这个比较难懂了，当存在素数是 i 的因子是就跳出循环，假设有一个合数 N = n 1 ∗ n 2 ∗ n 3 ∗ n 4 N = n1 * n2*n3*n4 N=n1∗n2∗n3∗n4，且假设 n 1 < n 2 < n 3 < n 4 n1<n2<n3<n4 n1<n2<n3<n4，很显然 n 1 ∗ n 2 ∗ n 3 n1*n2*n3 n1∗n2∗n3会先出现但是它乘以 n 1 n1 n1后就会跳出循环了，同理 n 1 ∗ n 2 ∗ n 4 ， n 1 ∗ n 3 ∗ n 4 n1*n2*n4，n1*n3*n4 n1∗n2∗n4，n1∗n3∗n4也乘不到对应的 n 3 n3 n3， n 2 n2 n2就会退出，只有 n 2 ∗ n 3 ∗ n 4 n2*n3*n4 n2∗n3∗n4这个天命之子会乘以 n 1 。 n1。 n1。综合上面两个过程大致可以证明每个合数只会被筛选一次。

还有其他筛选时间也是 o ( n ) o(n) o(n)的方法，等以后运用见到了再补充