埃拉托斯特尼筛法详解及实现_Marco&GalaxyDragon的博客-程序员秘密_埃拉托斯特尼筛法

技术标签: 算法  算法与数据结构  

埃拉托斯特尼筛法是一个快速获取小于数X的所有素数集合的算法。
首先我们要明确,假设一个合数x能表示为两个数的乘积,他必定有一个小于等于sqrt(x)的因子,这可以用归谬证明法证明。如果两个因子都大于sqrt(x),那么乘积大于x,这和假设矛盾。
所以,判断一个数x是否是合数,只要依次除以2至sqrt(x)间的素数,判断是否整除即可。

埃拉托斯特尼筛法基于以下原理,给定一个素数n>1,kn是一个合数(k>1),例如n=3,那么6,9,12,15…都是合数。

以100为例,我们先创建一个100个数字的数组。
先使用最小的素数2,将所有2的倍数(除2本身)标记为合数。
接下来2+1的数是3,此时检查3是不是素数,检查标记,发现没有被标记为合数(因为不是2的倍数),所以再将所有3的倍数标记为合数。
下一个数是4,发现他已经被标记为合数,所以他可以表示小于4的素数的乘积2*2,所以4的倍数必定含有因子2,所以所有4的倍数已经全部被标记过,直接跳过4。
下一个数是5,没有被标记为合数,把所有小于100的5的倍数标记为合数
………这样一直计算到sqrt(100),即10。
那么为什么不标记大于10的数例如11呢?因为所有的倍数已经被标记过了,例如22,33,44,55…分别有因子2,3,2,5,大于10的倍数,例如11*11已经超过max了,参见最上面的推论
注意这里有一个优化点,很多书籍上或者教程上都没有说出来,只要标记大于本身的倍数就行了,例如5,只要标记5*5,5*6,5*7…为合数,因为5*2,5*3,5*4…已经被之前出现的数的倍数标记过了

  static List<Integer> findPrimes(int max) {

        List<Integer> list = new ArrayList<>();
        //为了保持索引值与数值一致,看上去更清晰,先加一个0
        list.add(0);
        for (int i = 1; i <= max; i++) {
            list.add(i);
        }
        //1不是素数,去掉
        list.set(1, 0);

        int s = (int) Math.sqrt(max);
        //遍历小于sqrt(max)的数
        for (int i = 2; i <= s; i++) {
            //先判断是不是素数
            if (list.get(i) != 0) {
                //这里直接忽略了小于i的倍数,因为之前肯定已经出现过了。(这个优化很多别的地方都没有看到)
                int a = i * i;
                while (a <= max) {
                    list.set(a, 0);
                    a += i;
                }
            }
        }

        return list.stream().filter(i -> i != 0).collect(Collectors.toList());
    }

这样,最终就可以获取小于等于x的所有素数


该算法java实现参见我github
https://github.com/luckyCatMiao/AlgorithmPractice/blob/master/src/SieveofEratosthenes.java

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/o83290102o5/article/details/79491834

智能推荐

MacOS下载MySQLWorkbench8.0.23意外退出解决办法_李问号的博客-程序员秘密

MacOS下载MySQLWorkbench8.0.23意外退出解决办法MacOS11版本下载完MySQLWorkbench8.0.23,打开时显示意外退出,原因可能是目前apple还不支持MySQLWorkbench最新版。解决方法是先下载旧版本即MySQLWorkbench8.0.22版本。下载链接: https://dev.mysql.com/downloads/workbench/.下载过程非常简单,和下载其它软件没什么区别。成功下载并打开,配上实图:...

Linux 内核延时函数_与时俱进2014的博客-程序员秘密_linux内核延时

linux内核提供3个函数分别进行纳秒,微妙和毫秒延时:void ndelay(unsigned long nsecs);void udelay(unsigned long usecs);void mdelay(unsigned long msecs);这3个函数的延时原理是忙等待,也就是说在延时的过程中并没有放弃cpu,根据cpu的频率进行一定次数

LeakCanary:检测所有的内存泄露_傲慢的上校的博客-程序员秘密

本文译自:https://corner.squareup.com/2015/05/leak-canary.html(LeakCanary是由Square公司刚刚开源用于查找Android内存泄露的库) java.lang.OutOfMemoryError at android.graphics.Bitmap.nativeCreate(Bitmap.java:-2)

ProcessingJS介绍_赶路人儿的博客-程序员秘密_processing.js

最近由于工作的关系,好好研究了一下ProcessingJS。Processing是一门可视化编程语言,ProcessingJS是它的JavaScript实现,使用HTML5的canvas,配合现代浏览器来实现web客户端的可视化技术。(不得不说,John Resig真是个高产的作者,jQuery、Sizzle、ProcessingJS)ProcessingJS做了这两件事:1.把基于Jav...

Java基础第十八课(GUI图形用户界面)_周秃秃的博客-程序员秘密

前面我们一直都是用控制台进行信息的输入输出来写Java程序但是我们平常见到的程序都是有好看的界面的你可能会想难道Java不能做界面???放心,Java可以说是很强大的它是可以做出来的,只不过用Java写Windows窗口程序都太麻烦了所以用Java来写的不多但是我还是要讲一下滴好啦 开始一、简介及简单演示我们平时电脑用的软件能看到的界面其实就是GUI(Graphic User I...

USB xHCI控制器使用总结_静思心远的博客-程序员秘密_usb xhci

USB xHCI控制器使用总结1 Intel USB xHCI控制器1.1 驱动架构1.2 x86 OTG架构1.3 x86 xHCI Scheduler Async Delay1.4 Interrupt on Short Packet1.5 x86 USB DCI DbC调试技术1.6 reset USB device1.7 PIPE PHY数据线宽度2 Bulk传输速度计算3 xHCI HS眼图调试3.1 EHCI眼图调试寄存器设置流程3.2 xHCI每个port的4个寄存器3.3 xHCI HS眼图调

随便推点

openlayers学习二:画多边形_锦岁的博客-程序员秘密_openlayers画多边形

&lt;!DOCTYPE html&gt;&lt;html lang="en"&gt;&lt;head&gt; &lt;meta charset="UTF-8"&gt; &lt;title&gt;画多边形&lt;/title&gt; &lt;script src="dist/ol.js"&gt;&lt;/script&gt; &lt;link rel="styl...

vant 上传附件后回显_vant上传文件到后端_weixin_39964819的博客-程序员秘密

最近在做手机版页面,采用的vant框架,这个上传控件和以前用iview、element有点不一样,iview、element都是直接提供后端接口文件会自动发送到后端,vant需要自己负责发送文件到后端,对于我这种面向百度编程人员还是有点难度。特意记一下,能帮到其他面向百度编程人员代码很简单,基本是使用文件构建FormData参数,如下:html代码:after-read="afterRead":b...

云客Drupal源码分析之缓存系统Cache_u011474028的博客-程序员秘密

在介绍drupal8的缓存系统前我们先了解一下缓存系统的本质及特性,缓存的存在依赖于两个目的:节省资源和提高速度,起不到这两作用则缓存没有存在的必要,当一个结果需要进行大量计算才能得到,而它又不会频繁更新那么缓存结果可以节省大量算力,缓存的是一个结果,这个结果可以存放在多台服务器上面实现负载均衡,从而进一步提高访问速度,在高访问网站中缓存非常重要,drupal8的缓存设计也是围绕这两个目的而设计。

IDEA新建项目时,没有Spring Initializr选项_BedrockOfAI的博客-程序员秘密

  版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u012860950/article/details/76146072最近开始使用IDEA作为开发工具,然后也是打算开始学习使用spring boot。看着博客来进行操作上手spring boot,很多都是说创建一个新项目(Create New Project)选择 Spring...

jmeter实现多个请求并行执行,验证线程安全_我心依依旧的博客-程序员秘密_jmeter多个请求同时并发

最近有线上发现一个bug:多个业务场景并行请求,出现下发结果存在串的现象。一、现象描述如下图所示:两个不同策略出现串的情况二、压测原理新建测试计划时有个独立运行每个线程组选项1、勾选独立运行每个线程组选项(Run Thread Groups consecutively(i.e.one at time)),则表示顺序执行。顺序执行,指的是测试计划中存在多个线程组时,第一个线程组执行完后再...

scala mysql连接池_scala实现数据库的连接池(mysql数据库,scala-2.10.4)_weixin_40005437的博客-程序员秘密

使用jdbc提供的驱动进行连接数据库。首先需要从MySQL官网上下载jdbc的驱动,得到.jar文件,这就是我们需要的jdbc驱动。 我们需要连接数据库,就首先需要我们电脑上有MySQL的数据库,并建立一个表,来存放数据。这里我自己建立一个名为mydb的表。 建立好表后一、编写实现代码类:MySqlPoolpackage test.testConnectionPollimport java.sq...