《算法笔记》系列----质数的判断(埃氏筛法)

2024-03-30 09:52

本文主要是介绍《算法笔记》系列----质数的判断(埃氏筛法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一、朴素算法

二、埃氏筛法

1、与朴素算法对比

2、算法介绍    

3、例题即代码实现


一、朴素算法

  从素数的定义中可以知道,一个整数n要被判断为素数,需要判断n是否能被2.3.n- 1中的一个整除。只2,3..n- 1都不能整除n,n才能判定为素数,而只要有一个能整除n的数出现,n就可以判定为非素数。
        这样的判定方法没有问题,复杂度为0(n)。但是在很多题目中,判定素数只是整个算法
中的一部分,这时候0(n)的复杂度实际上有点大,需要更加快速的判定方法。注意到如果在
2 ~n-1中存在n的约数,不妨设为k,即n%k=0,那么由k*(n/k)=n可知,n/k也是n的一个约数,且k与n/k中一定满足其中一个小于等于sqrt(n)、另一个大于等于sqrt(n)其中sqr(n)为根号n。这启发我们,只需要判定n能否被2, 3,.. sqrt(n)中的一个整除(具中x表示对x向下取整),即可判定n县否为素数。这样的话时间复杂度就位o( sqrt(n))

代码如下:

bool isprime(int x){for(int i=2;i*i<=x;i++){if(x%i==0){return false;}}return true;
}

这里有个东西要注意:c++中sqrt函数是对double类型的函数,但是在实际代码中传进来的一般是一个int类型的数,因此我们在使用时要像下面这样让x乘上一个1.0

int main(){int x;cin>>x;ifprime(sqrt(1.0*x));}

二、埃氏筛法

1、与朴素算法对比

      上面这个算法在判断一个数是否是素数时时间复杂度优越,但是如果我们这个题目需要得到在这个数范围内所有的素数(素数表)时这个时间复杂度就偏大,即o(nsqrt(n))

2、算法介绍    

      因此我们要隆重引入我们新的算法埃氏筛法:

当需要生成一个给定范围内所有素数的素数表时,可以采用更高效的算法来降低时间复杂度。一种常见的方法是使用埃拉托斯特尼筛法(Sieve of Eratosthenes)

        埃氏筛法的时间复杂度O(nlog(log(n))),明显优于逐个判断每个数是否为素数的O(nsqrt(n)​)复杂度。

埃拉托斯特尼筛法的基本思想是从2开始,依次将每个素数的倍数标记为非素数,直到遍历完整个范围。剩下未被标记的数即为素数。

整理步骤如下:

  1. 初始化一个布尔数组,表示每个数是否为素数,初始值为True。
  2. 从2开始遍历到n​,对于每个素数p,将其倍数p×k(其中k>1)标记为非素数。
  3. 遍历完整个范围后,未被标记的数即为素数。

这种方法在生成素数表时能够显著减少时间复杂度,是常用的高效算法之一。

3、例题即代码实现

链接-晴问算法:https://sunnywhy.com/sfbj/5/4/205

完整ac代码:

 

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;vector<bool> isprime(n+1,true);for(int i=2;i<=n;i++){if(isprime[i]){for(int j=i+i;j<=n;j+=i){isprime[j]=false;}cout<<i<<endl;}}return 0;
}

这篇关于《算法笔记》系列----质数的判断(埃氏筛法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D

Python判断for循环最后一次的6种方法

《Python判断for循环最后一次的6种方法》在Python中,通常我们不会直接判断for循环是否正在执行最后一次迭代,因为Python的for循环是基于可迭代对象的,它不知道也不关心迭代的内部状态... 目录1.使用enuhttp://www.chinasem.cnmerate()和len()来判断for

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

如何测试计算机的内存是否存在问题? 判断电脑内存故障的多种方法

《如何测试计算机的内存是否存在问题?判断电脑内存故障的多种方法》内存是电脑中非常重要的组件之一,如果内存出现故障,可能会导致电脑出现各种问题,如蓝屏、死机、程序崩溃等,如何判断内存是否出现故障呢?下... 如果你的电脑是崩溃、冻结还是不稳定,那么它的内存可能有问题。要进行检查,你可以使用Windows 11

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个