素数打表法
2021/5/2 10:25:21
本文主要是介绍素数打表法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
定义法
素数的定义:
- 只能被1和本身整除的数。
适用范围:
- 适合判断单个数是否为素数
- 若是求一个大范围内的所有素数,此方法耗时太长
代码:
/*判断n是否为素数*/ for(i=2;i*i<=n;i++) { if(n%i==0) { flag=0;/*flag=0代表n不是素数*/ break; } }
普通筛选法/埃氏筛法
思想:
- 首先假定所求范围内的所有数都是素数,然后去除该范围内的所有合数,剩下的全是素数。
- 任何合数均可表示为素数的倍数。因此,如果已知一个数是素数,那么它的倍数都是合数。
代码:
int not_prime[MAXN]={0};/*假定所有数都是素数*/ for(int i=2;i<=sqrt(MAXN);i++) { if(!not_Prime[i]) {/*如果i是素数*/ for(j=i*i;j<=MAXN;j+=i) {/*那么i的倍数全是合数*/ not_prime[i]=1; } } }
注意事项:
- 为什么第二重循环里j的初始值为i* i呢?这是为了避免重复标记。举个例子,若i是素数,那么2* i、3* i、4* i……(i-1)* i分别是2、3、4……(i-1)的倍数,在外层循环循环到i之前就已经被标记为合数了。所以应该从j=i* i开始,依次把j+i、j+2* i……标记为合数。
缺陷:
对于一个合数,可能被重复筛选多次。
线性筛选法/欧拉筛法
思路:
欧拉筛法是埃氏筛法的改进版,大体思路都是先假定所有数都是质数,然后把所有合数去除,留下的都是质数;不同之处就是去除合数的方法,欧拉筛法保证了每个合数只会被它的最小质因数筛去。虽然代码有两重循环,但是因为待求范围内的每个数均只被筛选1次,所以时间复杂度是O(n)。
代码:
bool visit[MAXN]={0};/*visit数组存的是待求范围的所有自然数*/ /*visit[1]=0表示1是素数*/ int prime[MAXL]; /*prime数组只存待求范围内的素数*/ /*MAXL可以根据MAXN的大小大致估计一下,MAXN一般是题目给出*/ int cnt=0; /*cnt用来记录素数的个数*/ void getprime(int n) { for(int i = 2;i <= n;i++) { if(!visit[i]) prime[cnt++]=i;/*如果i是素数,就把i标记在prime数组里*/ for(j = 0;i * visit[j] < n && j < cnt;j++) { visit[i * prime[j]] = 1;/*prime数组里面存的素数的i倍,都标记为合数*/ if(i % prime[j] == 0) break;/*关键,看后面的解释*/ } } } `` ### 解释: 为什么说欧拉筛法保证了每个合数只会被它的最小质因数筛去呢? 关键是这一行: ```c if(i % prime[j] == 0) break;
接下来分类讨论一下:
- 如果i % prime[j] != 0,prime[j]一定小于i的最小质因数,所以prime[j]一定是i* prime[j]的最小质因数。
- 如果i % prime[j] == 0,
(1)prime[j]就是i的最小质因数(因为j是从小到大枚举的),此时prime[j]依旧是是i* prime[j]的最小质因数。
(2)但是j++后的下一个prime[j],就大于i的最小质因数,故prime[j]不是i* prime[j]的最小质因数。所以才要在i % prime[j] == 0
的时候break。
学自大佬,欢迎交流批评指正。
这篇关于素数打表法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现