[算法初阶]埃氏筛法与欧拉筛

素数的定义：

首先我们明白：素数的定义是只能整除1和本身（1不是素数）。

我们判断一个数n是不是素数时，可以采用试除法，即从i=2开始，一直让n去%i，直到i*i<=n

c语言:

#include<stdio.h>
int main()
{
    int n;
    for (int i = 2; i * i<= n; i++)
    {
        if (n % i == 0)
        {
            printf("%d 不是素数",n);
            return 0;
        }
    }
    printf("%d 是素数", n);
}

​

C++: 

#include<iostream>
using namespace std;
int main()
{
    int n;
    for (int i = 2; i * i<= n; i++)
    {
        if (n % i == 0)
        {
            cout<<n<<"不是素数";
            return 0;
        }
    }
    cout<<n<<"是素数";
}

​

但是问题来了，如果一两个数让你去判断，你这么试除一下还行，那要是一堆大且多的荒谬的数据让你去判断，你需要循环的次数也是一个天文数字。这个时候，我们就可以通过一些算法来实现对于大数据（大且多）素数的判断。

埃筛与欧拉筛的实质：

其实埃筛与欧拉筛的实质都且就是围绕这一句话：素数的倍数不是素数。

比如说让你输出100000——1e5内所有的素数

那我们就筛就好啦，首先咱需要创建一个存素数的数组和一个bool类型的数组（用来判断该元素是否是素数)

埃氏筛:

//埃氏筛法
int n=1e5;
bool shai[n];
int cun[n];
signed main()
{
    int cnt = 0;
    for (int i = 2; i <= n; i++)
    {
        if (!shai[i])//如果为0
        {
            cun[cnt++] = i;
            for (int j = 2; j <= n; j++)
            {
                if (i * j > n)break;//超过数据大小就退掉。
                shai[i * j] = 1;//1的都是素数的倍数——所以不是素数。
            }
        }
    }
    for (int i = 0; i < cnt; i++)
    {
        printf("%d ", cun[i]);
    }
}

我们先看一看欧拉筛

欧拉筛：

#include<iostream>
using namespace std;
bool a[100001] = { 1,1 };//同上问一样i=0,i=1的时候都不是质数 
int b[100001];//存质数 
long long n;
int main()
{
    int cnt = 0;
    cin >> n;//查的范围
    for (int i = 2; i <= n; i++)
    {
        if (a[i] == 0)    b[++cnt] = i;
        for (int j = 1; j <= cnt; j++)
        {
            if (i * b[j] > n)break;// 如果超出给出的范围，那么就退出循环 
            a[i * b[j]] = 1;//素数的倍数不是素数，进行标记。
            if (i % b[j] == 0)break;//超级关键的只标记一次
        }
    }
    for (int i = 1; i <= cnt; i++)
    {
        printf("%d ", b[i]);
    }
}

欧拉筛比埃筛要快很多很多

我们看看埃筛，就从2开始，它是素数，所以内循环会标记4,6,8,10,12······一直到退出循环，然后当外层循环到3的时候，它又会标记6,9,12······，在这里我们就能看出一点问题，有数被重新标记了，而且循环到后面重复标记的数量会很多,所以浪费了时间。

原文地址：https://blog.csdn.net/2301_80017277/article/details/143668418

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！