埃氏筛法与线性筛法

埃氏筛法

埃拉托斯特尼筛法,简称埃氏筛或爱氏筛,是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数,必须把不大于根号n的所有素数的倍数剔除,剩下的就是素数。

埃氏筛法即为古老的数学思想,常常用于其快速求取素数表

素数表的快速求取在一道算法题中是尤为关键的,特别是在对于数据量过大的时候,埃氏筛法能够节省大量的运算时间从而快速的完成需求目标,比较于我们在学习编程语言中利用数学库开方求取的算法,其能够遍历更少的元素,节省更多的时间,可以作为一个进阶来学习

无论是在c还是c++的学习当中,我们都曾学习过求取素数的算法

例如c语言版本求取0~n之间的所有素数

#include <stdio.h>
#include <math.h>
bool judge(int n)
{
	if(n == 0 || n == 1)return false;
	for(int i = 2;i <= sqrt(n);i ++ )
	{
		if(n % i == 0)return false;
	}
	return true;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i = 0;i <= n;i ++ )
	{
		if(judge(i))printf("%d ",i);
	}
	return 0;
}

例如c ++语言版本求取0~n之间的所有素数

#include <iostream>
#include <cmath>
using namespace std;
bool judge(int n)
{
	if(n == 0 || n == 1)return false;
	for(int i = 2;i <= sqrt(n);i ++ )
	{
		if(n % i == 0)return false;
	}
	return true;
}
int main()
{
	int n;
	cin >> n;
	for(int i = 0;i <= n;i ++ )
	{
		if(judge(i))cout << i << ' ';
	}
	return 0;
}

由此可见,其共同点都在于一个判断素数的函数,其为代码核心

bool judge(int n)
{
	if(n == 0 || n == 1)return false;
	for(int i = 2;i <= sqrt(n);i ++ )
	{
		if(n % i == 0)return false;
	}
	return true;
}

埃氏筛法的原理在于,通过对于最小的数字开始从小到大进行筛选,素数的定义是,这个数只可以被1和自身整除,因此凡是素数的倍数均不是素数,那么我们从0~20开始举例,通过埃氏筛法来求的话,首先为了减少运算,我们可以直接跳过0和1,直接从2开始筛选。

在进行2的筛选的时候,我们将0~20中所有2的倍数去掉,也就是4、6、8、10、12、14、16、18、20

而后进行3的筛选,将3的倍数筛掉,也就是6(已筛过)、9、12(已筛过)、15、18(已筛过)

再次枚举的时候就可以跳过4了,直接筛5,将10(已筛过)、15、20(已筛过)筛去

继续枚举的时候直接枚举7,筛掉7的倍数14(已筛过)

接下来就是一个不断枚举的过程:

跳过8、9、10枚举11,筛掉11的倍数

跳过12,枚举13,筛掉13的倍数

跳过14、15、16,枚举17,筛掉17的倍数

跳过18,枚举19,筛掉19倍数

跳过20,完成埃氏筛法,操作结束

此上内容为0~20利用埃氏筛法求取素数的详解

由此我们可以发现,埃氏筛法的特点在于在不断进行从0~n的枚举过程之中,一遍枚举一遍进行筛选后面的数字进行快速遍历,而后快速完成时间的判定,即在不断便利的过程之中,可以保证每一个遍历到的数字必为素数且可以快速跳过遍历

总解一句话就是:

先解释一下筛选法的步骤:

<1>先将1去掉

<2>将2的倍数去掉。

<3>将3的倍数去掉。

……

<i>将i的倍数去掉。

要得到不大于某个自然数N的所有素数,只要在2~n中将不大于sqrt(n)的素数的倍数全部划去即可

当然,这种情况的利用仅仅是用于确定判断素数,若是想要拉取素数表的话还是要遍历到n

标准代码为:

#include <iostream>
using namespace std;
const int N = 1e6+10;
int prime[N];
bool isprime[N];
int idx = 0;
int main()
{
	int n;
	cin >> n;
	for(int i = 0;i <= n;i ++ )isprime[i] = true;
	prime[0] = prime[1] = false;
	for(int i = 2;i <= n;i ++ )
	{
		if(isprime[i])
		{
			for(int j = 2 * i;j <= n;j += i)
			{
				isprime[j] = false;
			}
		}
		if(isprime[i])prime[ ++ idx ] = i;
	}
	for(int i = 1;i <= idx;i ++ )cout << prime[i] << ' ';
	return 0;
}

线性筛法 

在使用埃氏筛法的过程之中以及举例模拟时我们可以发现,埃氏筛法虽然比暴力筛法效率高,但是却有着后面元素被反复标记的情况出现,因此也就浪费了一些运算时间。在这里我们将介绍埃氏筛法的优化终极版,也就是线性筛法

线性筛法能够很好的解决元素被重复标记的现象,使后面的被标记元素仅仅被最小的质数因此筛一次(),因此能够减少重复标记的操作,从而使效率最大化

#include <iostream>
using namespace std;
const int N = 1e6+10;
int prime[N];
bool isprime[N];
int idx = 0;
int main()
{
	int n;
	cin >> n;
	for(int i = 2;i <= n;i ++ )
	{
		if(!isprime[i])
		{
			prime[ ++ idx ] = i;
		}
		for(int j = 1;j <= idx && i <= n / prime[j];j ++ )//i * prime[j] <= n有可能会爆int,在这里我们使用等价变式 
		{
			isprime[i * prime[j]] = 1;
			if(i % prime[j] == 0)break;
		}
	}
	for(int i = 1;i <= idx;i ++ )cout << prime[i] << ' ';
	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/943331.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

流批一体向量化计算引擎 Flex 在蚂蚁的探索和实践

编者按&#xff1a;Flex是蚂蚁数据部自研的一款流批一体的向量化引擎&#xff0c;Flex是Fink和Velox的全称&#xff0c;也是Flexible的前缀&#xff0c;被赋予了灵活可插拔的寓意。本文将重点从向量化技术背景、Flex架构方案和未来规划三个方面展开论述。 作者介绍&#xff1a;…

Pytorch | 利用I-FGSSM针对CIFAR10上的ResNet分类器进行对抗攻击

Pytorch | 利用I-FGSSM针对CIFAR10上的ResNet分类器进行对抗攻击 CIFAR数据集I-FGSSM介绍I-FGSSM代码实现I-FGSSM算法实现攻击效果 代码汇总ifgssm.pytrain.pyadvtest.py 之前已经针对CIFAR10训练了多种分类器&#xff1a; Pytorch | 从零构建AlexNet对CIFAR10进行分类 Pytorch…

全面Kafka监控方案:从配置到指标

文章目录 1.1.监控配置1.2.监控工具1.3.性能指标系统相关指标GC相关指标JVM相关指标Topic相关指标Broker相关指标 1.4.性能指标说明1.5.重要指标说明 1.1.监控配置 开启JMX服务端口&#xff1a;kafka基本分为broker、producer、consumer三个子项&#xff0c;每一项的启动都需要…

HTML制作一个普通的背景换肤案例2024版

一&#xff0c;完整的代码&#xff1a; <!DOCTYPE html> <html lang"zh"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>换肤</t…

《计算机组成及汇编语言原理》阅读笔记:p86-p115

《计算机组成及汇编语言原理》学习第 6 天&#xff0c;p86-p115 总结&#xff0c;总计 20 页。 一、技术总结 1.if statement 2.loop 在许多编程语言中&#xff0c;有类种循环&#xff1a;一种是在程序开头检测条件(test the condition),另一种是在程序末尾检测条件。 3.C…

CSS(三)盒子模型

目录 Content Padding Border Margin 盒子模型计算方式 使用 box-sizing 属性控制盒子模型的计算 所有的HTML元素都可以看作像下图这样一个矩形盒子&#xff1a; 这个模型包括了四个区域&#xff1a;content&#xff08;内容区域&#xff09;、padding&#xff08;内边距…

MySQL外键类型与应用场景总结:优缺点一目了然

前言&#xff1a; MySQL的外键简介&#xff1a;在 MySQL 中&#xff0c;外键 (Foreign Key) 用于建立和强制表之间的关联&#xff0c;确保数据的一致性和完整性。外键的作用主要是限制和维护引用完整性 (Referential Integrity)。 主要体现在引用操作发生变化时的处理方式&…

MySQL从入门到入土---MySQL表的约束 (内含实践)---详细版

目录 引入&#xff1a; null 与not null default&#xff1a; comment列描述 &#xff1a; not null 和 default&#xff1a; zerofill &#xff1a; 主键&#xff1a;primary key 复合主键&#xff1a; 自增长:auto_increment 唯一键&#xff1a;unique key 外键&a…

基于NodeMCU的物联网窗帘控制系统设计

最终效果 基于NodeMCU的物联网窗帘控制系统设计 项目介绍 该项目是“物联网实验室监测控制系统设计&#xff08;仿智能家居&#xff09;”项目中的“家电控制设计”中的“窗帘控制”子项目&#xff0c;最前者还包括“物联网设计”、“环境监测设计”、“门禁系统设计计”和“小…

Webpack在Vue CLI中的应用

webpack 作为目前最流行的项目打包工具&#xff0c;被广泛使用于项目的构建和开发过程中&#xff0c;其实说它是打包工具有点大材小用了&#xff0c;我个人认为它是一个集前端自动化、模块化、组件化于一体的可拓展系统&#xff0c;你可以根据自己的需要来进行一系列的配置和安…

java日志框架:slf4j、jul(java.util.logging)、 log4j、 logback

SLF4J--抽象接口 SLF4J (Simple Logging Facade for Java) 是一个为各种 Java 日志框架提供简单统一接口的库。它的主要目的是将应用程序代码与具体的日志实现解耦&#xff0c;使得在不修改应用程序代码的情况下&#xff0c;可以轻松地切换不同的日志框架。 jul-to-slft4j.ja…

命令行之巅:Linux Shell编程的至高艺术(中)

文章一览 前言一、输入/输出及重定向命令1.1 输入/输出命令1.1.1 read命令1.1.2 echo命令 1.2 输入/输出重定向1.3 重定向深入讲解1.4 Here Document1.4.1 /dev/null 文件 二、shell特殊字符和命令语法2.1 引号2.1.1 双引号2.1.2 单引号2.1.3 倒引号 2.2 注释、管道线和后台命令…

一文理解机器学习中二分类任务的评价指标 AUPRC 和 AUROC

&#x1f349; CSDN 叶庭云&#xff1a;https://yetingyun.blog.csdn.net/ 在机器学习的二分类任务中&#xff0c;评估模型性能是至关重要的一步。两种常用的评价指标是 Precision-Recall Curve 下的面积 (AUPRC) 和 Receiver Operating Characteristic Curve 下的面积 (AUROC)…

Visual Studio Code(VS Code)配置C/C++环境

一、Visual Studio Code安装 Visual Studio Code&#xff0c;下文中简称为VS Code的详细安装方法请参考VSCode安装教程&#xff08;超详细&#xff09;-CSDN博客 二、MinGW编译器下载与配置 1、MinGW介绍 MinGW(Minimalist GNU for Windows)是一款用于Windows 平台的轻…

少儿编程在线培训系统:客户服务与学习支持

2.1 VUE技术 VUE它是由HTML代码&#xff0c;配上嵌入在HTML代码里面的Java代码组成的应用于服务器端的语言&#xff0c;使用VUE进行开发能够更加容易区分网页逻辑以及网页设计内容&#xff0c;让程序员开发思路更加清晰化&#xff0c;VUE在设计组件时&#xff0c;它是可以重用的…

uniapp Native.js原生arr插件服务发送广播到uniapp页面中

前言 最近搞了个设备&#xff0c;需求是读取m1卡&#xff0c;厂家给了个安卓原生demo&#xff0c;接入arr插件如下&#xff0c;接入后发现还是少了一部分代码&#xff0c;设备服务调起后触发刷卡无法发送到uniapp里。 中间是一些踩坑记录&#xff0c;最后面是解决办法&#xf…

C项目 天天酷跑(下篇)

上篇再博客里面有&#xff0c;接下来我们实现我们剩下要实现的功能 文章目录 碰撞检测 血条的实现 积分计数器 前言 我们现在要继续优化我们的程序才可以使这个程序更加的全面 碰撞的检测 定义全局变量 实现全局变量 void checkHit() {for (int i 0; i < OBSTACLE_C…

HarmonyOS NEXT 实战之元服务:静态案例效果--航空出行

背景&#xff1a; 前几篇学习了元服务&#xff0c;后面几期就让我们开发简单的元服务吧&#xff0c;里面丰富的内容大家自己加&#xff0c;本期案例 仅供参考 先上本期效果图 &#xff0c;里面图片自行替换 效果图1完整代码案例如下&#xff1a; import { authentication } …

福特汽车物流仓储系统WMS:开源了,可直接下载

导语 大家好&#xff0c;我是社长&#xff0c;老K。专注分享智能制造和智能仓储物流等内容。欢迎大家到本文底部评论区留言。 近日&#xff0c;福特汽车公司推出了其广受好评的仓库管理系统GreaterWMS&#xff08;更大仓库管理系统&#xff09;的开源版本&#xff0c;意味着各行…

STM32完全学习——FLASH上FATFS文件管理系统

一、需要移植的接口 我们通过看官网的手册&#xff0c;可以看到我们只要完成下面函数的实现&#xff0c;就可以完成移植。我们这里只移植前5个函数&#xff0c;获取时间的函数我们不在这里移植。 二、移植接口函数 DSTATUS disk_status (BYTE pdrv /* Physical drive nmuber…