素数筛(埃拉托斯特尼筛法 VS 欧拉筛法)_好好学习多挣钱的博客-程序员秘密

技术标签: 数论  

推荐使用欧拉筛法,是线性筛法

import java.util.Arrays;

/**
 * 埃拉托斯特尼筛法 VS 欧拉筛法(更优化)
 * 
 */
public class Main {

    private static final int MAX_LENGTH_CHECK = 100000000;          // 亿
    private static final int MAX_LENGTH_PRIMELIST = 10000000;       // 千万

    private static boolean[] check = new boolean[MAX_LENGTH_CHECK]; // 存储标记
    private static int[] primeList = new int[MAX_LENGTH_PRIMELIST]; // 存储素数
	


   public static void main(String[] args) {
        int n = 100000; // 十万
        long start = System.currentTimeMillis();
        Eratosthenes(n);
        long end = System.currentTimeMillis();
        System.out.println("十万级别数量:埃氏筛,耗时:" + (end - start) + " ms");

        Arrays.fill(check, false);
        Arrays.fill(primeList, 0);

        start = System.currentTimeMillis();
        Euler(n);
        end = System.currentTimeMillis();
        System.out.println("十万级别数量:欧拉筛法,耗时:" + (end - start) + " ms");
    }

}
  /**
     * 埃拉托斯特尼筛法(简称埃氏筛或爱氏筛):要得到自然数n以内的全部素数,必须把不大于 根号n 的所有素数的倍数剔除,剩下的就是素数。
     * 例如:给出要筛数值的范围n,找出以内的素数。
     * 解法:先用2去筛,即把2留下,把2的倍数剔除掉;再用下一个质数,也就是3筛,把3留下,把3的倍数剔除掉;接下去用下一个质数5筛,把5留下,把5的倍数剔除掉;不断重复下去......。
     * 
     * 时间复杂度:O(nloglogn) 
     * 不足之处:6 在 indexI = 2 时被标记,而在 indexI = 3 时,又被标记了一次。存在重复标记,有优化空间
     */
    private static void Eratosthenes(int num) {
        int count = 0;
        for (int indexI = 2; indexI <= num; indexI++) {
            // 当 indexI 不是被剔除的数时,将 indexI 留下
            if (!check[indexI]) {
                primeList[count++] = indexI;
            }
            // 剔除 indexI 的倍数
            for (int indexJ = indexI + indexI; indexJ <= num; indexJ += indexI) {
                check[indexJ] = true;
            }
        }
    }

    /**
     * 欧拉筛法:保证每个合数只会被它的最小质因数筛掉,时间复杂度降低到O(n)。 
     * 每一个数都去乘以当前素数表里面已有的数,当 indexI 是合数,且 indexI % primeList[indexJ] == 0 时,只能乘以第一个素数 2
     */
    private static void Euler(int num) {
        int count = 0;
        for (int indexI = 2; indexI <= num; indexI++) {
            if (!check[indexI]) {
                primeList[count++] = indexI;
            }
            // 每一个数都去乘以当前素数表里面已有的数,如果 indexI 是合数,且 indexI % primeList[indexJ] == 0,那么它只能乘以第一个素数 2
            // 如:2×2、3×(2、3)、4×(2)、5×(2、3、5)、6×(2)、7×(2、3、5、7)、8×(2)、9×(2、3)、10×(2)
            for (int indexJ = 0; indexJ < count; indexJ++) {
                // 过大的时候跳出
                if (indexI * primeList[indexJ] > num) {
                    break;
                }
                check[indexI * primeList[indexJ]] = true;
                // 如果 indexI 是一个合数,而且 indexI % primeList[indexJ] == 0
                // 保证了每个合数只会被它的最小素因子筛掉
                if (indexI % primeList[indexJ] == 0) {
                    break;
                }
            }
        }
    }
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/DavidSharch/article/details/99707027

智能推荐

npx:调用项目内部安装的模块___Charming__的博客-程序员秘密

背景最近在学gulp时,在局部安装了gulp,然后直接在终端使用gulp --tasks,结果报错'gulp' 不是内部或外部命令,也不是可运行的程序或批处理文件。我认真想了一下,因为我的包是装在项目内的(局部的),没有在环境变量里注册,当然就不能在终端直接使用了。(注:全局安装的node包是可以在终端直接使用的)那有没有办法在终端直接使用呢?有的。类似这样吧,直接进入node-m...

JS节点操作(2)- 创建节点,添加节点,删除节点,复制节点_Moony_wy的博客-程序员秘密_js添加节点

JS节点操作(2)- 创建节点,添加节点,删除节点,复制节点node.appendChild(child) 添加到子元素数组的末尾node.insertBefore(child, 指定元素) 添加到指定子元素的前面node.removeChild(child) 删除指定子节点,返回删除的节点cloneNode() 复制节点复制节点要注意,cloneNode()括号里面为空或是false则为浅拷贝,只复制标签不复制里面的内容。cloneNode(true) 括号里为true则为深拷贝,复制标签和内容

php支付宝接口开发提现,ThinkPHP3.2集成 “单笔提现到支付宝账号接口”_绿皮工业的博客-程序员秘密

/*** 首先要确保应用已在支付宝开放平台上线,才能调用相关接口* 先将下载的支付宝服务端sdk全部放在 ThinkPHP/Library/Vendor 目录下,并改名为 alipay-sdk*/Vendor('alipay-sdk.AopSdk');$aop = new AopClient ();$aop-&gt;gatewayUrl = 'https://openapi.alipay.com/...

flutter1.9升级flutter2.0错误整理_傻瓜搬砖人的博客-程序员秘密_flutter 升级2

flutter 2.0 变化还是比较大了,好多代码都变了,下面整理一些升级过程中遇到的错误.1 resizeToAvoidBottomPaddingcity_pickers插件:resizeToAvoidBottomPadding:false, 改为 resizeToAvoidBottomInset: false,2.Error: No named parameter with the name ‘shadowThemeOnly’../../flutter/.pub-cache/hosted/p

利用Python导入csv数据到ElasticSearch_能想多少想多少的博客-程序员秘密

from elasticsearch import helpers,Elasticsearchimport csvcsvFile=r'A:\develop\APB_Production\13_APB_res\20190904_RES.csv'csvFile1=r"A:\develop\APB_Production\13_APB_res\20190908_RES.csv"es=Elast...

随便推点

php 个人账户转账,支付宝单笔转账到支付宝个人账户接口 ( PHP 版 )_weixin_39942351的博客-程序员秘密

alipay.fund.trans.toaccount.transfer(单笔转账到支付宝账户接口)单笔转账到支付宝账户接口是基于支付宝的资金处理能力,为了满足支付宝商家向其他支付宝账户转账的需求,针对有部分开发能力的商家,提供通过 API 接口完成支付宝账户间的转账的功能。 该接口适用行业较广,比如商家间的货款结算,商家给个人用户发放佣金等。注意事项:1.目前仅支持账户余额渠道付款。2.转账额度...

蓝桥杯 算法提高 凶手_一叶之修的博客-程序员秘密

一道推断题算法提高 凶手Description   巴斯维克命案抓住了六个嫌疑犯,他们的口供如下:  A:我不是罪犯  B:A、C中有一个是罪犯  C:A和B说了假话  D:C和F说了假话  E:其他五个人中,只有A和D说了真话  F:我是罪犯  他们中只有一半说了真话,凶手只有一个。  本题可能有多种可能性,即正确答案(找到唯一的凶手)可能有多...

矩池云配置MMDetection环境+训练自己的数据集_yezzii的博客-程序员秘密_矩池云配置环境

自用,方便查找。参考:采用矩池云配置MMDetection环境_一只大憨憨的博客-程序员秘密_矩池云配置环境环境镜像:Pytorch1.5.0镜像描述:预装:Python3.8, CUDA 10.1, cuDNN 7.6, Pytorch 1.5.0,Ubuntu18.04步骤安装环境:1. 安装torchconda install pytorch==1.6.0 torchvision==0.7.0 cudatoolkit=10.1 -c pytorch -y...

SEDA架构_lxlzhn的博客-程序员秘密_seda架构

纯粹转发,没有深入研究,转自:SEDA架构笔记一、传统并发模型的缺点基于线程的并发特点:每任务一线程直线式的编程使用资源昂高,context切换代价高,竞争锁昂贵太多线程可能导致吞吐量下降,响应时间暴涨。基于事件的并发模型特点:单线程处理事件每个并发流实现为一个有限状态机应用直接控制并发负载增加的时候,

ubuntu中eclipse无法识别android手机问题_梁瑾的博客-程序员秘密

问题:在ubuntu中eclipse中用真机来调试androi程序时,发现无法识别手机,如下图显示2.37一栏之前显示全是乱码,这是解决后截的图。问题原因是:在window下我们可以通过安装驱动来实现abd的连接,而在ubuntu下就没有安装手机驱动这个概念,那我们肯定也需要个啥来实现这个驱动功能。这个android官网介绍得很详细。记录下解决步骤如

推荐文章

热门文章

相关标签