程序员经验分享-hwhale

素数打表，复杂度（Onlogn）和O（n）(对与10^7来说线性快两倍） + 分解质因数

2023-11-09

代码：

接口：    primeInit(100000);//打表的范围

素数存在primeList中，个数为primeCount

typedef long long LL;
int const MAXN = 10000100;
bool isPrime[MAXN];
LL primeList[MAXN/10],primeCount = 0;

void primeInit(LL n)
{

    memset(isPrime,true,sizeof(isPrime));//初始化认为全部是素数
    int m = sqrt(n + 0.5);
    isPrime[1] = false;
    for(int i = 2; i <= m;  i ++)
    {
        if(isPrime[i])//判断是素数
        {
            for(int j = i * i; j <= n; j += i){

               isPrime[j] = false;
            }
        }
    }
    for(int i = 2; i <= n; i ++)
    {
        if(isPrime[i]){

        primeList[primeCount] = i;
                primeCount ++;
        }

    }
}


代码：接口primeInit(n)//n表示要求素数的范围

typedef long long LL;
int const MAXN = 10000100;
bool isPri
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

ACM

算法

素数筛选法

Eratosthense筛法

hdu 5778

素数打表，复杂度（Onlogn）和O（n）(对与10^7来说线性快两倍） + 分解质因数 的相关文章

  • RISC-V、ARM和X86架构

    1 要了解X86 ARM和RISC V架构的区别 就得先了解复杂指令集 CISC 和精简指令集 RISC A X86使用的是复杂指令集 CISC ARM和RISC V使用的是精简指令集 RISC 这便是属于这几种架构之间最大的区别 狭义的x

随机推荐

  • javaweb使用Thymeleaf 最凝练的CRUD项目-上

    目录 最凝练的CRUD 1 建模 物理建模 逻辑建模 2 总体架构 3 搭建持久化层所需环境 导入jar包 创建jdbc properties 创建JDBCUtils工具类 BaseDao 4 搭建表述层所需环境 导入jar包 创建View

  • 力扣(19) - 跳跃游戏

    给定一个非负整数数组 nums 你最初位于数组的 第一个下标 数组中的每个元素代表你在该位置可以跳跃的最大长度 判断你是否能够到达最后一个下标 示例 1 输入 nums 2 3 1 1 4 输出 true 解释 可以先跳 1 步 从下标 0

  • a*算法的优缺点_轻松理解机器学习算法-朴素贝叶斯

    1 预备知识 贝叶斯定理 Bayes theorem 是概率论中的一个定理 它跟随机变量的条件概率以及边缘概率分布有关 通常事件A在事件B发生的条件下的概率 与事件B在事件A发生的条件下的概率是不一样的 然而这两种是有确定关系的 这种关系就

  • ASP.NET Core 简介

    NET Core 是 NET Framework 的新一代版本 是微软开发的第一个具有跨平台 Windows Mac OSX Linux 能力的应用程序开发框 ASP NET Core 是 Microsoft 新开发的 基于 NET Cor

  • JSON

    数据提取之JSON与JsonPATH JSON JavaScript Object Notation 是一种轻量级的数据交换格式 它使得人们很容易的进行阅读和编写 同时也方便了机器进行解析和生成 适用于进行数据交互的场景 比如网站前台与后台

  • 20181220_eglSwapBuffers详解

    eglSwapBuffers详解 问题来自eglSwapBuffers是否有等待 如果调用eglSwapBuffers的话 是不是会导致帧率下降 2 7 1 BootAnimation中的调用 之所以需要了解这个api的具体实现 因为我们需

  • 标准DH建模与改进DH建模（二）—— 什么是改进DH法以及为什么要学？

    学习机器人建模并不是一个愉快的过程 不愉快的一个重要原因就是 建模得到的方程又臭又长 仅仅是计算一次也许都要花不少时间 更不要说除了正逆运动学方程 你还要需要动力学方程 甚至动力学参数标定方程 当你掌握了DH建模方法后 你会陷入短暂的满足感

  • Python APP自动化测试详解

    一 App自动化测试简介 随着移动互联网的发展 越来越多的App产品应运而生 很多公司除了Web产品外还研发了相应的手机App产品 一些公司的主营业务甚至就是App 测试工程师也需要掌握一定的App端测试技能 从而让自己从烦琐 重复的 点点

  • HTTP Status 500 - An exception occurred processing JSP page /WEB-INF

    HTTP Status 500 An exception occurred processing JSP page WEB INF test showCountry jsp at line 11type Exception reportme

  • 支付宝同步跳转和异步通知简要介绍

    支付宝同步跳转和异步通知简要介绍 同步跳转文件 return url php 异步通知文件 notify url php 用户支付完之后会直接执行return url php 只执行一次 我们在这个文件里写的代码用于修改数据库订单状态 改为

  • 史上最简单Robotium跨进程操作实践——基于ADB框架

    楼主原创 分享不易 转载请注明出处 谢谢 2015年2月3日更新 有些朋友在用真机尝试本方法时 抛出了InputStream cannot be null的异常 该异常是由于adb运行在robotium框架中时 是完全运行在手机中的 此时它

  • SFTP文件上传下载

    http www cnblogs com longyg archive 2012 06 25 2556576 html 转载 转载于 https www cnblogs com sunfb p 4330324 html

  • 将一个TXT文件里面数据读出 ，进行数据去重处理 ，写入文件

    总的来说 分为三个模块 读文件模块 处理数据 写入文件 中间有如何创建文件 public class EG Reader 主方法 public static void main String args String filePath C U

  • JS中this.x= x

    今天看代码的时候发现了如上图的一个写法 虽然大致猜测到了其 的用法 但还是在网上求证了一下 那么JS中this x x 0的 是什么意思呢 在 js 中 这相当于一个赋值语句 只要 x 的值不返回为 false 那么就把 x 的值赋值给th

  • 解决安装Ubuntu &Debian ，安装界面黑屏或者只显示一个短白线问题

    AMI BIOS 可以关闭8254 Clock Gating 在重新安装 路径 Chipset South Cluster Configuration Miscellaneous Configuration 8254 Clock Gatin

  • 无线通信原理期末复习提纲

    文章目录 无线通信原理期末复习提纲 一 名词解释 1 同频再用距离 2 多径效应 3 多普勒效应 4 区群 5 越区切换 6 OFDMA 7 OFDM 8 TDMA 9 FDD 10 CSMA 二 简答题与计算 第一章 1 蜂窝网基本原理

  • 查成语--每天10行python代码系列！

    在爬取成语2 每天10行python代码系列一文中爬取了该网站收录的所有成语 并写入了sqlite数据库 数据存储的格式为每条记录存储一个成语以及成语的拼音 释义 出处和示例 这里实现了在命令行查询成语的功能 查询时通过 blur开关指定是

  • 【STM32标准库】【基础知识】程序烧录

    文章目录 开发板和烧录器 USB烧录 1 安装STM32CubeProgrammer 2 生成HEX文件 3 选择烧录模式 4 进入ISP模式 5 设置软件烧录 STLINK烧录 1 驱动下载 2 电路连接 3 Keil设置 4 烧录 ke

  • thingsboard 服务器mqtt设备过一段时间会自己断开，断开之后就不能发消息了QoS=2

    使用things board最新社区版 MQTT为V3 1 使用MQTT设备连接后能正常发布与订阅 但是一段时间后发现设备就不能再发布消息了 客户端也没有显示连接断开 检查后发现是客户端设备使用的消息可靠性QoS 2 修改客户端设备的发布Q

  • 素数打表，复杂度（Onlogn）和O（n）(对与10^7来说线性快两倍） + 分解质因数

    代码 接口 primeInit 100000 打表的范围 素数存在primeList中 个数为primeCount typedef long long LL int const MAXN 10000100 bool isPrime MAXN

热门标签