埃拉托斯特尼筛法(埃筛)_hambaga的博客-程序员秘密_埃拉托斯特尼筛法

技术标签: 算法模板  

埃筛的作用是找出区间内的所有素数,复杂度是O(nloglogn)。其基本思想是:素数的倍数一定是合数。

#include <bits/stdc++.h>
using namespace std;
const int Max = 1e5;
int n;
int prime[Max]; // 1表示是素数

void eratos() {
    
	memset(prime, 1, sizeof(prime)); // 默认全是素数
	prime[0] = prime[1] = 0; // 0和1不是素数
	for (int i = 2; i * i <= n; i++) {
     // 当i*i>n时,i*j>n,内层循环一定不执行,白白浪费时间
		if (!prime[i]) continue;
		for (int j = i * 2; j <= n; j+=i) {
    
			prime[j] = 0; // 素数的倍数一定是合数
		}
	}
}

int main() {
    
	cin >> n;
	eratos();
	for (int i = 0; i <=n; i++) if (prime[i]) cout << i << endl;
    return 0;
}

注意外层循环的条件是 i * i <= n,当 i 更大时,内层循环一定不执行,等于是浪费时间。
该程序可以在1秒内找出1e6范围以内的全部素数,了解即可,做题时应使用更高效的线性筛素数算法(欧拉筛法)。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Kwansy/article/details/103558991

智能推荐

BOOST 编译_alger_lzl的博客-程序员秘密

bjam stage --toolset=msvc-9.0 --stagedir="D:\boost_1_47_0" link=static runtime-link=static threading=multi debug releasebjam stage--toolset=msvc-9.0--stagedir="D:\boost_1_47_0" link=shared run

【Java日期类Date、LocalDate、LocalTime、 LocalDateTime及转换】_Rita_zzf的博客-程序员秘密_java localdatetime转date

目录日期类 Date世界标准时间 (GMT=UTC)获取日期对象及获取时间毫秒数的两种方法:Date对象获取所有日期数据Date对象获取年 月 日 时 分 秒时间补零占位方法抽取获取时间日期SimpleDateFormat实现日期格式化与时间字符串解析日期比较与标准时间转换日期比较标准时间转换时区转换与构造方法将时间毫秒数转为日期对象时区转换时间毫秒数转为日期对象日期类 Date世界标准时间 (GMT=UTC)GMT:格林威治标准时间 1900-01-01 00:00:00从19 世纪中叶起,世界

教你THINKPHP6.0 快速安装使用MongoDB_IronMenPHP的博客-程序员秘密_mongodb thinkphp

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档文章目录前言 一、pandas是什么? 二、使用步骤 1.引入库 2.读入数据 总结前言 MongoDB是非关系型数据库中的文档数据库。MongoDB是为快速开发互联网Web应用 而设计的数据库系统。 MongoDB的设计目标是极简、灵活、作为 Web应用栈的一部分。 MongoDB的数据模型是面向文档的,所谓文档是一种类似于JSON的结构,简单理解 MongoDB这个数据库中存的是各种各样的 JSO

websocket网络断开之后重连_Axchen519的博客-程序员秘密_websocket断开重连

websocket网络断开之后重连最近做了一个web的聊天页面,加载到APP中聊天使用,后来发现手机锁屏一分钟之后socket资源就会被关闭,这时解锁再发消息就会失败,所以需要对websocket做重连,废话不多说,贴代码&lt;html lang="en"&gt;&lt;head&gt; &lt;meta charset="UTF-8"&gt; &lt;meta name="viewport" content="width=device-width, user-s

解决pytorch半精度amp训练nan问题_视学算法的博客-程序员秘密

点击上方“视学算法”,选择加"星标"或“置顶”重磅干货,第一时间送达作者 | 可可哒@知乎(已授权)来源 | https://zhuanlan.zhihu.com/p/443166496...

随便推点

报名 | EOS智能合约与DApp开发,学技术+拿大奖,等你发车!_区块链大本营的博客-程序员秘密

比特币被称为区块链1.0,因为它开辟了数字加密货币的天下,走出了从0到1的决定性一步。以太坊被称为区块链2.0,因为它提供了可运行智能合约的图灵完备的虚拟机,带来了无限的...

精灵宝可梦需考虑季节因素_chuochifang9028的博客-程序员秘密

从夏天开始,《精灵宝可梦Go》就红遍全球。现在虽然热度没有当开始那么高了,但是它依然在iOS游戏收入排行榜上名列前茅。在万圣节系列特别活动中,《精灵宝可梦Go》的全球每日活跃玩家总数暴增13.2%。在美国地区,每日活跃玩家总数高达19.2%。 10月,《精灵宝可梦Go》在全美iOS游戏收入榜...

2021运营App推广必备的几款工具_Xinstall渠道统计的博客-程序员秘密_app推广工具

app推广的方法多种多样,不同的推广方法所得到的效果和获得的指标数据都是有很大的差别的,而目前市场上的app推广方法其中的主流就是付费广告渠道,通过在各大相关的平台和渠道上面付费投放app宣传广告,短期内获得大量的流量。而本文要给大家介绍的app推广运营工具,希望能够帮助大家更好的去做app的推广和运营工作。1、思维导图工具:ProcessOnProcessOn是一个在线协作绘图平台,为用户提供强大、易用的作图工具!支持在线创作流程图、思维导图、组织结构图、网络拓扑图、BPMN、UML图、UI界面原型设

favicon.ico 图标及时更新问题_webysp的博客-程序员秘密_favicon更新

首先看你 favicon.ico 图标文件引入路径是否正确<link type="image/x-icon" href="./favicon.ico" rel="icon">然后 看ico文件能否正常打开,这两个没问题的话,在地址栏直接输入你的域名 http://xxx.com/favicon.ico 注意 此刻可能还是 之前的ico图标 不要着急 刷新一下 试试 完美解决 清除程序缓存

Delphi——数组(静态数组和动态数组)、地址和指针_Christine666666的博客-程序员秘密_delphi数组地址

1-Delphi支持的数组类型有两种:静态数组和动态数组静态数组——声明时就已经确定大小的数组类型;动态数组——其大小在声明时不能确定的数组,其数组大小在使用时确定。2-数组的声明及引用数组元素1) 静态数组声明****一维数组规则:只需声明数组的长度和数据类型即可语法:var World:array[0**…**5] of char;含义:声明一个成员是char即字符类型的数组,数组名字为World;数组的长度是5,即索引是从0到5;静态数组的声明及引用****一维数组例如:proc

利用ShellExecuteEx手动提升用户特权,以管理员权限来运行程序_yousss的博客-程序员秘密_shellexecuteex 权限

#include &amp;lt;stdio.h&amp;gt;#include&amp;lt;windows.h&amp;gt;#include&amp;lt;tchar.h&amp;gt; int _tmain(int argc,TCHAR* argv[]){SHELLEXECUTEINFO sei={sizeof(SHELLEXECUTEINFO)};sei.lpVerb=TEXT(&quot;runas&quot;);sei...

推荐文章

热门文章

相关标签