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

相关文章

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程