关于质数筛——数论

1年前作者：c++小蒟蒻分类：Toy博客阅读(12)违法举报

这篇具有很好参考价值的文章主要介绍了关于质数筛——数论。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

埃式筛法

#include <bits/stdc++.h>
using namespace std;
bool vis[100000010];	//标记数组 
int n;
int main(){
	scanf("%d",&n);
	vis[0]=vis[1]=1;
	for(int i=2;i*i<=n;i++){	//优化1 
		if(vis[i]!=1){
			for(int j=i*i;j<=n;j+=i){	//优化2 
				vis[j]=1;	//0是质数，1不是 
			}
		}
	}
	for(int i=2;i<=n;i++){
		if(vis[i]==0){
			cout<<i<<" ";
		}
	}
	return 0;
}

欧拉筛

#include <bits/stdc++.h>
using namespace std;
bool vis[100000010];
int n,cnt=0,prime[10000000];
int main(){
	scanf("%d",&n);
	vis[0]=vis[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]){
			prime[++cnt]=i;
		}
		for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0){
				break;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(prime[i]==0)
			break;
		printf("%d ",prime[i]);
	}
	return 0;
}

文章来源地址https://www.toymoban.com/news/detail-613001.html

到了这里，关于关于质数筛——数论的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：

领支付宝红包赞助服务器费用

蓝桥杯数论必考算法------快速幂
我们练习一下： 2.1快速幂之迭代版 O(n∗logb) 2.2快速幂之递归版 O(n∗logb)
2024年02月12日
浏览(8)
C++算法之旅、08 基础篇 | 质数、约数
在1的整数中，如果只包含1和本身这两个约数，就被称为质数(素数) 866. 试除法判定质数 - AcWing题库 (O(n)) 约数 d 与 n / d 成对出现，可以枚举较小的那一个 (O(sqrt{n})) (d = n/d \\\\ d^2 = n \\\\ d = sqrt{n}) 难点循环判断条件不要用 sqrt，每次循环都会执行一遍sqrt函数，比较慢循环
2024年02月08日
浏览(12)
c++入门必学算法质数筛
质数筛也叫素数筛，是求1到n之内素数的优化算法，质数筛有两种，埃氏筛和欧拉筛。埃氏筛的时间复杂度接近O(n*logn)，而欧拉筛可以把复杂度降低到O(n)，下面看两种算法的到底是如何一步步优化的吧暴力法求解复杂度O(n)* n sqrt{n} n ，是新手必学的算法，能解决小数据的
2023年04月21日
浏览(11)
数论——欧几里得算法、裴蜀定理、扩展欧几里得算法学习笔记
最大公约数最大公约数即为 Greatest Common Divisor，常缩写为 gcd。一组整数的公约数，是指同时是这组数中每一个数的约数的数。 (pm 1) 是任意一组整数的公约数；一组整数的最大公约数，是指所有公约数里面最大的一个。特殊的，我们定义 (gcd(a, 0) = a) 。最小公倍数最
2024年02月08日
浏览(17)
【数论】扩展欧几里得算法（EXTENDED-EUCLID）
本文整理梳理了一些有关扩欧算法的内容，力求深入浅出便于理解，对一些作者在初次接触此算法时的不解（比如一些不是很好看出来的“易得”“显然”hh）通过数学形式呈现与推导。本文涉及的数学推导非常简单。代码均采用C++。限于作者能力有限可能有些地方表述不清
2024年02月17日
浏览(9)
数论 --- 约数和定理公式推导、最大公约数、欧几里得算法
和试除法判断一个数是不是质数是一个道理从小到大枚举所有的约数，如果当前数能整除这个数的话，说明这个数就是当前数的约数优化，与试除法判断质数是一样的如果 d 是 n 的约数，n / d 也一定能整除 n，一个数的约数也一定是成对出现的，在枚举的时候也可以只枚举
2023年04月08日
浏览(12)
[数论第二节]欧拉函数/快速幂/扩展欧几里得算法
欧拉函数 (varphi(N)) : 1-N中与N互质的数的个数若 (N = p_1^{a_1} · p_2^{a_2} · p_3^{a_3} ··· ·p_n^{a_n}) 其中p为N的所有质因子则 (varphi(N) = N(1-frac{1}{p_1})(1-frac{1}{p_2})···(1-frac{1}{p_n})) 证明：互质：两数的公共因子只有1 去掉所有与N有(大于1的)公共因子的数，剩下的数就是与
2024年02月14日
浏览(10)
【算法每日一练]-数论（保姆级教程篇3 ）#越狱 #找朋友 #全部相同 #方形 #tax
目录今日知识点：基于涂色问题的组合数求所有数的最大公约数阶乘质因数分解哥德巴赫猜想越狱找朋友全部相同方形 tax 监狱有n个房间，每个房间关一个犯人，有m种宗教，一个犯人信仰一种。如果相邻的房间犯人信仰同一种宗教就会越狱。
2024年02月03日
浏览(12)
[Go版]算法通关村第十三关黄金——数字数学问题之数论问题（最大公约数、素数、埃氏筛、丑数）
题目链接：LeetCode-1979. 找出数组的最大公约数辗转相除法其核心部分为：若r 是a ÷ b的余数，则 gcd(a, b)=gcd(b, r) 题目链接：LeetCode-204. 计数质数如果 x 是质数，那么大于 x 的 x 的倍数 2x,3x,… 一定不是质数。时间复杂度分析：外层循环的迭代次数是 n-2，即 O ( n ) O(n) O ( n ) 次
2024年02月11日
浏览(15)
C语言判断一个数是否是质数的几种常用方法（求100-1000以内的所有质数）
要用代码判断一个数是否是质数，首先我们需要知道什么什么数称之为质数。质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。以下有三种方法判定质数：通过从2到n-1每个数均整除
2024年02月08日
浏览(49)