【素数判断】埃氏筛法和欧拉筛法（线性筛法）

本是古典何须时尚 2023-01-10 10:28 160阅读 0赞

## 埃氏筛法 ##

埃氏筛法的原理是：  
给出要筛数值的范围n，找出以内的素数。  
先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去…。

**任何一个大于1的自然数 N，如果N不是素数，都可以唯一分解成有限个素数的乘积。**

例如：8 = 2 \* 2 \* 2 ； 6 = 3 \* 2 ……

代码实现一：

bool is_prime[100]; // 这里这个数组全部初始化为0了
    
    void init()
    {
        
    	for(int i=2;i<100;++i)
    	{
        
    		is_prime[i]=1;
    	}
    }
    
    void judge_prime()
    {
        
    	init(); // 调用init函数，让is_prime数组初始化值为1
    	for(int i=2;i<sqrt(100);i++)
    	{
        
    		if(is_prime[i]==1) 
    		{
        
    			for(int j=i*i;j<100;j+=i)
    			{
        
    				is_prime[j]=0;
    			}
    		}
    	}
    }

代码实现二：

bool vis[maxN];
    
    void init()
    {
        
        memset(vis,false, sizeof(vis));//所有数初始化为0->质数
        vis[0]=true;
        vis[1]=true;
    }
    
    void Is_Prime()
    {
        
        init();
        for(int i=2;i<=maxN;i++)
        {
        
            if(!vis[i])
                for(int j=i*i;j<=N;j+=i)
                    vis[j]=true;
        }
    }

memset是个啥  
memset:作用是在一段内存块中填充某个给定的值，它对较大的结构体或数组进行清零操作的一种最快方法。

如果要把一个char a[20]清零, 一定是 memset(a, 0, 20)

## 欧拉筛法（线性筛法） ##

线性筛法的原理是：  
首先，我们要知道，埃氏筛法无法避免重复筛选（比如30 = 2 \* 15 ， 那么30这个数，在2的时候会处理一次，在15的时候又会处理一次）。所以为了避免重复筛选，有了线性筛法。  
线性筛是在埃氏筛法的基础上，让每一个合数（除了素数以外的数），只被它的最小质因子筛选一次，达到不重复的目的。

**每次只要筛选小于等于i的第一个素因子的素数与i的乘积**

bool vis[maxN];
    int prime[maxN],cnt;
    
    void init()
    {
        
        memset(vis,false, sizeof(vis));//所有数初始化为0->质数
        vis[0]=true;
        vis[1]=true;
        cnt=0;
    }
    
    void Is_Prime()
    {
        
        init();
        for(int i=2;i<=N;i++)
        {
        
            if(!vis[i])//i是质数
                prime[++cnt]=i;//prime是用来存质数的数组，显然数组中的质数是从小到大
            for(int j=1;j<=cnt;j++)
            {
        
                if(i*prime[j]>N)//超出了范围
                    break;
                vis[i*prime[j]]=true;
                if(i % prime[j] == 0)//跑到了i的最小的质因数
                    break;
            }
        }
    }