埃筛

作者 : 开心源码 本文共464个字,预计阅读时间需要2分钟 发布时间: 2022-05-13 共270人阅读

埃筛

给定一个整数N,求出1~N之间的所有质数,称为质数的挑选问题。埃筛线筛都是用于处理这个问题的算法。
埃筛的思想是任意一个整数x的倍数2*x,3*x,...都不是质数。从2开始,从小到大扫描每一个x,将他的倍数2*x,3*x,...,\lfloor N/x\rfloor *x一律标记为合数。
优化策略1,对于4来说,4的倍数都已经被2标记过一次了。没有必要在进行一次标记。假如一个数x是合数,那么他的倍数会被比x小的数,并且是x的质因数标记过。没有必要在标记一次。
优化策略2,对于5来说,10被2标记了,15被3标记过,20被2标记过。当我们标记p*x时,假如p<x那么p*x已经被p的质因子标记过了。没有必要在进行标记了。
假如我们只采用优化策略1,那么每个数x,会被他的不同的质因数标记一次。例如12会被2和3标记一次。int范围内的数最大的合数也只会被标记10次。埃筛的时间复杂度非常接近线性。

void primes(int n){  memset(v,0,sizeof(v))  for(int i = 2;i<=n;i++){  if(v[i])continue;  for(int j = i;j<=n/i;j++) v[i*j] = 1;  }}
说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 埃筛

发表回复