美文网首页
判断素数-埃氏筛法的详解

判断素数-埃氏筛法的详解

作者: 是落阳呀 | 来源:发表于2019-12-03 12:27 被阅读0次

埃氏筛法

一个判断素数的高效算法

关于埃氏筛法的百度百科解释在这里埃拉托斯特尼筛法,当然我不可能给个百度百科的解释就撤,那会被打死的。
众所周知,素数指的是除了1和它本身之外没有其它约数的数
我们假定一个数num,那么如果我们想通过编程来判断它是不是素数,我们首先通过它的定义想到暴力枚举方法,即用for循环配合取模操作实现,c++代码如下

bool flag = true; // flag作为标志来标识这个数是不是素数,默认设置为true
for(int i=2;i<num/2;i++)
{
    if(num % i == 0)
    {
        flag = false; // 如果能被整除了,那就不是素数,退出循环
        break;
    }
}
if(flag)
{
    cout<<"数:"<<num<<"是素数"<<endl;
}

当然这种方法就显得很麻烦,虽然直观易懂,但是时间复杂度达到了n^2级。
当然如果稍微改进一点的话就会知道把我上面的代码循环中的i < num/2改成i*i < num,时间可以缩短。但是仍不够明显。


快乐的分割线


下面我们开始埃氏筛法的学习

看过上图百度百科的同学应该明白,埃氏筛法是范围判断素数的方法,即,你给出一个数n,我用埃氏筛法能判断从1-n的所有素数出来。

原理

素数的倍数肯定不是素数

给定一个数n,我们开一个大小为n+1的bool型数组,即 bool nums[n+1] ,并全部初始化为false, 在这里声明一点,这个数组的 nums[0] 与 nums[1] 我们并不会使用到。
建立了这样一个数组之后,我们就可以直接开干啦,我们首先要找到最小的素数,即2,从而开始循环开炮
OK非常棒,现在我们已经能找出素数中的最小者了,任务完成一半!
接下来,我们应用我们的原理——素数的倍数肯定不是素数
这里有张表

是否是素数
2
3
4 不是(通过素数2的倍数判断)
5
6 不是(通过素数2,3的倍数判断)
7
8 不是(通过素数2的倍数判断)
9 不是(通过素数3的倍数判断)
加入我们要求10以内的素数,开一个nums[11],然后定位找到最小的素数->2,以2为基点,开炮,把2的倍数全部打死,当然这个也是有范围的,2的倍数我们只要判断到小于n就可以了,即小于10。然后2的倍数打死完了,再找幸存的最小素数3,以3为基点,开炮,在3的炮火攻击下,上次侥幸存活的9被揪出来打死了。***我们会一直判断,直到我们的基点达到一个临界点——小于等于n的开根号,这样我们就把所有潜藏的合数敌人全部消灭了,不信你瞅瞅? ***

原理如此,接下来附上这一部分的代码,看完代码之后我会有一个小小的问题遗留给大家思考

int main() // 这里只给出实现代码了,上面的头文件什么的都没写了
{
    int num;
    cin >> num;
    bool* nums = new bool[num];   // 这里我们如果需要用变量创建数组的话必须这样创建喔!
    for (int i = 0; i < num; i++)
    {
        nums[i] = true;
    }
    int sn = sqrt(num);
    for (int i = 2; i <= sn; i++) /* 从最小的素数2开始开炮*/
    {
        if (nums[i])
        {
            for (int j = i * i; j < num; j+=i)  // 此处需要注意,我们开炮的时候,第一颗炮弹直接打到i的平方上,这是避免了重复判断,j每次要增长i
            {
                nums[j] = false;   // 跟我一起,开炮!!
            }
        }
    }
    for (int i = 2; i < num; i++)
    {
        if (nums[i])
        {
            cout << i << "\t";  // 打印出选出来的素数你看看,这里我喜欢用制表符,个人习惯,看着舒服
        }
    }

    delete []nums;  // 最后可别忘了释放指针内存哦,并且将指针置空,养成好习惯,不要野指针!
    nums = nullptr;
    return 0;
}

好了,代码部分结束,最后我还遗留一个问题,你们有没有发现,我们这里重复判断了?比如我已经判断12是偶数了,已经杀死了,但是我以3为基点开炮的时候,还是会再打它一次,炸尸,这会不会浪费我们的炮弹资源(时间)呢?该如何改进这个问题呢?思考一下?

谢谢你来看我!

相关文章

  • 素数相关问题练习 C++

    辗转相除 素数判定 埃氏筛法

  • 判断素数-埃氏筛法的详解

    埃氏筛法 一个判断素数的高效算法 关于埃氏筛法的百度百科解释在这里埃拉托斯特尼筛法,当然我不可能给个百度百科的解释...

  • 204. Count Primes

    n以内素数的个数。 参考:埃拉托斯特尼筛法和素数判断 代码:

  • 机试常用算法和题型-数学专题

    数学专题,模拟 素数问题,普通筛和埃氏筛 另一种筛法,连续素数求和得超级素数 质因数 奇数魔方图 求小数的循环部分...

  • 判断素数-埃氏筛法的更优化,欧拉筛法的详解

    这个线性复杂度的欧拉素数筛法,爱了爱了 今天讲一下关于欧拉筛法的原理和代码实现,实不相瞒,我也才刚get到这个筛法...

  • 数论

    数学问题 1. 质数筛 埃氏筛 利用当前已经找到的素数,从后面的数中筛去当前素数的倍数,由预备知识一可知,当前素数...

  • noip模板整理

    数论快速幂高精度加法减法乘法除法线性筛素数埃氏筛法 O(nlglgn)最大公约数(gcd)最小公倍数(lcm)扩展...

  • 埃氏筛(求素数)

    众多筛法中最简单且容易理解的一种,时间复杂度为O(nloglogn),在找到一个素数后,马上将所求范围内该素数的倍...

  • 求小于等于n的质数个数

    埃氏筛法(Eratosthenes筛选法)算法基本思想:要得到自然数n以内的全部素数,必须把不大于n1/2的所有素...

  • 质因子分解(素数埃氏筛法)[PAT A1059]

    埃氏筛法原理质因子分解结论

网友评论

      本文标题:判断素数-埃氏筛法的详解

      本文链接:https://www.haomeiwen.com/subject/gsrcgctx.html