c++浅析素数原理和埃拉托斯特尼筛法(埃筛)

2023-12-01 07:10

本文主要是介绍c++浅析素数原理和埃拉托斯特尼筛法(埃筛),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

(以下图片来自wikipedia)

素数定理

我们先来看一个问题,对于一个不超过n的正整数,其中有多少是素数:

这就需要用到一个老朋友

我们高中经常见到的一个函数

\pi (x) \sim \frac{x}{lnx}

其中 \pi (x) 表示不超过x的素数的个数

上述函数表示不超过素数的数量可以用x/lnx来拟合

那么对于100个数中,就能大概计算出素数的个数约为22个,实际为25个

这样在做题时就可以大约估计出区间内素数的个数

Eratosthenes筛法

又称埃筛,是判断素数最为常见的一种筛法

所谓“筛”,是一种形象化的描述,我们设置的条件就如筛子上的孔,筛掉的杂质就是我们不需要的

合数,留下来的精品就是我们需要的素数

一个好的“筛子”,空的大小要合理,排布要准确,如果一个一个筛去,便会十分费力

所以我们要优化孔,是其筛的效率更高

对于每一个素数p,筛掉p的倍数,当筛完一轮之后(见文章开头的图),剩下的便是素数

下面给出代码

//to find the prime among 1 and nfor(int i = 2; i <= n; i ++){for(int j = i * 2; j <= n; j+= i) prime[j] = false;}

对于第二行循环的条件,我们解释一下

其中先令j是i = 2的2倍(因为2是素数),每次都递增i的一倍,即j = 4 -> j = 6 -> j = 8...

每次i的递增,当i等于3时,j起始为6,然后为9...

当i = 4时,会发现4已经被筛掉了,这里可以引出欧拉筛,一种更为巧妙的筛法,但在这里先不做介绍

...

以此类推,就如同开头的图一样,把质数的倍数全部筛掉了!

多么简单而又高效的一种算法!

时间复杂度分析

我们对程序的时间复杂度进行一次分析

对于每一个i值,内部循环的次数越是(想一想为什么,很简单!)

\frac{n}{i} 

即当i=2时,即为n/2

对于多次,并求和相加,便得到

\frac{n}{2} + \frac{n}{3} + \frac{n}{4} + \frac{n}{5}.....+\frac{n}{n}

 想一想这像什么?有没有想到把n做为因子提出来

没错,就是泰勒展开式

所以其复杂度为 O(nlogn) 

这样的运行效率已经很高了,为了更高,我们可以降低我们区间的范围

对于一个自然数来说,只要通过在\sqrt{n}的范围内的素数,就能筛掉n范围内的所有合数

为什么呢?

很简单,我们先来看一个数 72

他的约数有(1,72), (2, 36), (3, 24), (4, 18), (6,12), (9, 8)

会发现,72的平方根约为8.4, 而每个约数对里必有一个小于8.4的数,所以只要能判定

\sqrt{n}的范围内的素数,就能筛掉n范围内的所有合数

所以只需限定一个sqrt(n)的条件即可

 

这篇关于c++浅析素数原理和埃拉托斯特尼筛法(埃筛)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/440263

相关文章

Golang HashMap实现原理解析

《GolangHashMap实现原理解析》HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持高效的插入、查找和删除操作,:本文主要介绍GolangH... 目录HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

《SpringBoot循环依赖原理、解决方案与最佳实践(全解析)》循环依赖指两个或多个Bean相互直接或间接引用,形成闭环依赖关系,:本文主要介绍SpringBoot循环依赖原理、解决方案与最... 目录一、循环依赖的本质与危害1.1 什么是循环依赖?1.2 核心危害二、Spring的三级缓存机制2.1 三

C#中async await异步关键字用法和异步的底层原理全解析

《C#中asyncawait异步关键字用法和异步的底层原理全解析》:本文主要介绍C#中asyncawait异步关键字用法和异步的底层原理全解析,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录C#异步编程一、异步编程基础二、异步方法的工作原理三、代码示例四、编译后的底层实现五、总结C#异步编程

浅析Java中如何优雅地处理null值

《浅析Java中如何优雅地处理null值》这篇文章主要为大家详细介绍了如何结合Lambda表达式和Optional,让Java更优雅地处理null值,感兴趣的小伙伴可以跟随小编一起学习一下... 目录场景 1:不为 null 则执行场景 2:不为 null 则返回,为 null 则返回特定值或抛出异常场景

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

Go 语言中的select语句详解及工作原理

《Go语言中的select语句详解及工作原理》在Go语言中,select语句是用于处理多个通道(channel)操作的一种控制结构,它类似于switch语句,本文给大家介绍Go语言中的select语... 目录Go 语言中的 select 是做什么的基本功能语法工作原理示例示例 1:监听多个通道示例 2:带