[素数筛][容斥原理]:埃拉托斯特尼筛法

2023/11/30 9:23:54

求解问题:不超过一个给定正整数N的素数的个数

方法介绍:

根据合数的性质:一个合数可以被一个不超过它的平方根的素数整除

这里举例N=100:

介绍:为了找出不超过100的素数个数,首先根据合数的性质可以知道:100的合数一定有一个不超过10的素因子。因为小于10的素数仅有:2,3,5,7,因此不超过100的素数就是这4个素数以及那些大于1和不超过100且不被2,3,5,7整除的正整数。

应用容斥原理:我们令P1:整数能被2整除   P2:整数能被3整除    P3:整数能被5整除  P4:整数能被7整除。

于是答案就是:4+N[{P1}'{P2}'{P3}'{P4}']

关于N[{P1}'{P2}'{P3}'{P4}']解释:同时不满足P1,P2,P3,P4性质的个数

ps:已知结论:在1-N之间,有\left \lfloor \frac{N}{x} \right \rfloor个能被x整除的数

由于存在99个比1大且不超过100的正整数,所以由容斥原理说明:

N[{P1}'{P2}'{P3}'{P4}']=99-N[P1]-N[P2]-N[P3]-N[P4]+N[P1P2]+N[P1P3]+N[P1P4]+N[P2P3]+N[P2P4]+N[P3P4]-N[P1P2P3]-N[P1P2P4]-N[P1P3P4]-N[P2P3P4]+N[P1P2P3P4]

不超过100(且大于1)并被{2,3,5,7}的子集中的所有素数整除的正整数个数是\left \lfloor \frac{100}{N} \right \rfloor,其中N是这个子集中的素数之积。(因为任意两个素数都没有公因子)。因此:

N[{P1}'{P2}'{P3}'{P4}']=99-\left \lfloor \frac{100}{2} \right \rfloor-\left \lfloor \frac{100}{3} \right \rfloor-\left \lfloor \frac{100}{5} \right \rfloor-\left \lfloor \frac{100}{7} \right \rfloor+\left \lfloor \frac{100}{2\times 3} \right \rfloor+\left \lfloor \frac{100}{2\times5} \right \rfloor+\left \lfloor \frac{100}{2\times7} \right \rfloor+\left \lfloor \frac{100}{3\times5} \right \rfloor+\left \lfloor \frac{100}{3\times7} \right \rfloor+\left \lfloor \frac{100}{5\times7} \right \rfloor-\left \lfloor \frac{100}{2\times3\times5} \right \rfloor-\left \lfloor \frac{100}{2\times3\times7} \right \rfloor-\left \lfloor \frac{100}{2\times5\times7} \right \rfloor-\left \lfloor \frac{100}{3\times5\times7} \right \rfloor+\left \lfloor \frac{100}{2\times3\times5\times7} \right \rfloor

ans: 

N[{P1}'{P2}'{P3}'{P4}']=99-50-33-20-14+16+10+7+6+4+2-3-2-1-0+0=21

因此存在:4+N[{P1}'{P2}'{P3}'{P4}']=25个不超过100的素数

ps:有趣的是,这个算法求解素数个数的时间复制度为:O(1).....qwq


http://www.jnnr.cn/a/369260.html

相关文章

Docker详解,windows上安装与使用

Hi I’m Shendi Docker详解,windows上安装与使用 Docker详解 Docker 容器是一个开源的应用容器引擎,让开发者可以以统一的方式打包他们的应用以及依赖包到一个可移植的容器中,然后发布到任何安装了docker引擎的服务器上(包括流行的…

面试时被问:为什么裁员只裁你,不裁别人,该怎么回答?

面试官总有各种奇奇怪怪的问题,比如这个:为什么裁员裁了你,而不是裁别人?这个充满恶意的问题该怎么回答?网友给出了各种各样的答案,有人说,就说行业动荡,不稳定。有人说,…

Golang每日一练(leetDay0023)

目录 67. 二进制求和 Add Binary 🌟 68. 文本左右对齐 Text Justification 🌟🌟🌟 69. x 的平方根 Sqrt x 🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C…

vscode软件设置头文件路径的方法

一. 设置头文件路径原因 在使用 vscode 软件进行 C 开发过程中,有些 .c 文件引用的头文件,提示会找不到头文件路径。因此,vscode 软件需要设置头文件路径。 二. vscode设置头文件路径 在 vscode 软件打开的情况下,默认打开一…

UNIX环境高级编程——UNIX基础知识

1.1 引言 所有操作系统都为它们所运行的程序提供服务,典型的服务包括: 执行新程序打开文件读文件分配存储区获得当前时间… 1.2 UNIX体系结构 可将操作系统定义为一种软件,它控制计算机硬件资源,提供程序运行环境,…

JAVA打飞机游戏的设计与实现

手机软件现状 在信息社会中,手机及其他无线设备越来越多的走进普通百姓的工作和生活,随着信息网络化的不断进展,手机及其他无线设备上网络势在必行。但是传统手机存在以下弊端: 1. 传统手机出厂时均由硬件厂商固化程序&#xf…

Spring Boot使用GraphQL开发Web API

目录前言Spring Boot中GraphQL的实现方案前言 传统的Restful API 存在诸多的问题,首先它无法控制返回的字段,前端也无法预判后端的返回结果,另外不同的返回结果对应不同的请求地址,这就导致了多次请求的问题。而GraphQL正是基于这…

9.网络爬虫—MySQL基础

网络爬虫—MySQL基础MySQL安装教程MySQL登录Mysql数据库操作显示数据库创建数据库删除数据库查询数据库使用数据库Mysql数据类型Mysql数据表创建Mysql增删查改PyMysql安装Python的MySQL库连接数据库增添字段操作游标PyMysql插入PyMysql查询PyMysql更新PyMysql删除前言&#xff…

生成式 AI 背后的共同框架:Stable Diffusion、DALL-E、Imagen

前言 如果你对这篇文章感兴趣,可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」,查看完整博客分类与对应链接。 框架 这些生成式 AI 的整体功能为:输入「文字」,返回「图像」,即 Text-to-image Gener…

计算机发展史之阿达·洛芙莱斯

你一定想不到世界上最早的程序员竟然是一位女士,而且还有专门的编程语言为了纪念她而命名,她就是阿达洛芙莱斯(Ada Lovelace) 奥古斯塔阿达拜伦是她的原名,因为嫁给威廉金后晋封为洛芙莱斯伯爵,而后改的名字…

R -- 卡方检验--原理及应用

1.单样本方差同质性检验 2.适合性/拟合优度/吻合性检验 或者公式书写如下: 图片来源:https://www.bilibili.com/opus/730576389651038260?fromsearch&spm_id_from333.337.0.0 例题 3.独立性检验 如何理根据列联表推算论值 E11 sum(Row1) * sum(…

(九)大数据实战——hadoop集群的历史服务器配置与日志聚集

前言 前面的章节我们已经介绍过了关于hadoop集群部署的内容,延续上一节的内容。本节我们主要介绍一下关于hadoop集群历史服务器的配置与启动,方便我们查看hadoop操作过程中的一些任务执行情况。同时我们也配置一下hadoop集群的日志聚集功能,…

linux系统安装JDK(我的系统是ubunut20.04)

一、下载jdk包 # 下载解压wget https://download.oracle.com/java/17/latest/jdk-17_linux-x64_bin.tar.gztar -zxvf jdk-17_linux-x64_bin.tar.gz # 将jdk-17改名为javamv jdk-17 java# 拷贝到/usr/local目录下sudo cp -rap java /usr/local 二、添加环境变量 # 进入profile文…

信息系统项目管理师第四版知识摘编:第13章 项目资源管理​

第13章 项目资源管理​ 项目资源管理包括识别、获取和管理所需资源以成功完成项目的各个过程,这些过程有助于确保项目经理和项目团队在正确的时间和地点使用正确的资源。​ 13.1管理基础​ 13.1.1相关术语和定义​ 1项目团队​ 项目团队是执行项目工作&#xf…

linux入门---程序地址空间

之前学习的地址空间 在之前的学习中我们知道操作系统将内存划分为好几个区域,比如说栈区,堆区,未初始化区,已初始化区,代码区,每个区的大小不同所对应的功能也不同,并且在内存中每个字节大小的…

还在用xmind破解版?快来康康这个,墙裂推荐

我之前一直在用XMind破解 首先不是不支持,只是囊中有点羞涩....... 言归正传,我很是特别喜欢XMind的这些小功能,简直是神助攻 XMind 推荐指数:☆☆☆☆☆ 点击直达 >>XMind.cn 01 一键提取风格 魔力值 No.1 的非创建风…

【进阶C语言】各大常用库函数的模拟实现

前言 今天恒川带给大家的是平常应用的库函数,恒川来给大家都模拟实现一下,希望对大家有帮助!! 各大常用库函数的模拟实现1. 模拟实现strlen2. 模拟实现strcpy3. 模拟实现strcat4. 模拟实现strstr5. 模拟实现strcmp6. 模拟实现memc…

[Java] synchronized的锁优化机制

目录 一 . 锁膨胀(锁升级) 二 . 锁消除 三 . 锁粗化 附加 : Callable 接口 ReentrantLock ReentrantLock 与 synchronized 的区别 Semaphore (信号量) CountDownLatch 多线程下使用哈希表 1. HashTable 2 .ConcurrentHashMap ConcurrentHashMap 优点 CopyOnWri…

华为交换机 链路聚合

前言 随着网络规模不断扩大,用户对骨干链路的带宽和可靠性提出了越来越高的要求。在传统技术中,常用更换高速率的接口板或更换支持高速率接口板的设备的方式来增加带宽,但这种方案需要付出高额的费用,而且不够灵活。 采用链路聚合…

Java锁深入理解2——ReentrantLock

前言 本篇博客是《Java锁深入理解》系列博客的第二篇,建议依次阅读。 各篇博客链接如下: Java锁深入理解1——概述及总结 Java锁深入理解2——ReentrantLock Java锁深入理解3——synchronized Java锁深入理解4——ReentrantLock VS synchronized Java锁…
最新文章