埃氏筛法(埃氏算法)

阳光穿透心脏的1/2处 2023-09-28 16:07 22阅读 0赞

## 埃氏筛法 ##

> 埃拉托色尼筛选法，简称埃氏筛法， 是针对自然数列中的自然数而实施的，用于求一定范围内的质数。也就是给定整数n，求小于n的所有质数（素数）。  
> 埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

![在这里插入图片描述][8138b94cc760489ab86a38f3db4f4e76.png_pic_center]

## 埃氏筛法的基本思想 ##

> 埃氏筛法的基本思想 ：从2开始，将每个质数的倍数都标记成合数，以达到筛选素数的目的。

## 埃氏筛法的缺陷 ##

> 埃氏筛法的缺陷 ：对于一个合数，有可能被筛多次。例如 30 = 2*15 = 3*10 = 5\*6……（那么如何确保每个合数只被筛选一次呢？我们只要用它的最小质因子来筛选即可）。

## JAVA 代码案例 ##

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

![在这里插入图片描述][fdfe0f1cd7e242b1971fd41a3bbd6b4a.gif_pic_center]

1.  首先将0、1排除：
2.  创建从2到n的连续整数列表，\[2,3,4,…,n\]；
3.  初始化 p = 2，因为2是最小的质数；
4.  枚举所有p的倍数(2p,3p,4p,…)，标记为非质数（合数）；
5.  找到下一个 没有标记 且 大于p 的数。如果没有，结束运算；如果有，将该值赋予p，重复步骤4;
6.  运算结束后，剩下所有未标记的数都是找到的质数。

public static void main(String[] args) {
        
        int aa[] =new int[100];
        aa[2] =0;
        int k=2,tt=0;
        while(tt<101){
        
            //将不是素素的数筛出
            for(int i=1; i<aa.length;i++)
                if(i%k==0&&i!=k) aa[i] =1;
            //将筛选后的第一个数当做新的筛子
            for(int i=1;i<aa.length;i++){
        
                if(i>k&&aa[i]==0){
        
                    k=i;
                    break;
                }
            }
            tt++;
        }
        for(int i=1;i<aa.length;i++)
            if(aa[i]==0)
                System.out.printf("%d\t",i);
    }

![在这里插入图片描述][7d0fc3850ffe42a1ab99361309da9d30.png]

## 关联算法文章： ##

> 这里有一些相关的文章，可以参考一下

1、[斐波那契数列的迭代算法和递归算法][Link 1]  
2、[埃氏筛法(埃氏算法)][Link 2]  
3、[BF算法（暴⼒算法）-- 模式匹配算法][BF_--]  
4、[数据结构：八大数据结构分类][Link 3]  
5、[JAVA中 常用七大排序算法][JAVA_]  
6、[Linked 链表反转 - 迭代 与 递归][Linked _ - _ _]

[8138b94cc760489ab86a38f3db4f4e76.png_pic_center]: https://img-blog.csdnimg.cn/8138b94cc760489ab86a38f3db4f4e76.png#pic_center
[fdfe0f1cd7e242b1971fd41a3bbd6b4a.gif_pic_center]: https://img-blog.csdnimg.cn/fdfe0f1cd7e242b1971fd41a3bbd6b4a.gif#pic_center
[7d0fc3850ffe42a1ab99361309da9d30.png]: https://img-blog.csdnimg.cn/7d0fc3850ffe42a1ab99361309da9d30.png
[Link 1]: https://blog.csdn.net/GoodburghCottage/article/details/125929088
[Link 2]: https://blog.csdn.net/GoodburghCottage/article/details/125912135
[BF_--]: https://blog.csdn.net/GoodburghCottage/article/details/125907253
[Link 3]: https://blog.csdn.net/GoodburghCottage/article/details/125681654
[JAVA_]: https://blog.csdn.net/GoodburghCottage/article/details/125594490
[Linked _ - _ _]: https://blog.csdn.net/GoodburghCottage/article/details/125597183