什么是质数

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。 —百度

怎么判断质数

1.暴力判断

直接枚举 $i:2\rightarrow n-1$ ，如果 $i$ 是 $n$ 的因数，则 $n$ 一定是质数，如果找完都没找到这样的 $i$ 说明 $n$ 是合数，纯粹是根据定义来判断

bool check(int n){ if(n<2) return false; for(int i=2;i<n;i++){ if(n%2==0) return false; } return true; }

2.优化的暴力枚举

考虑到如果一个数 $i$ 为 $n$ 的因数，则 $\frac{n}{i}$ 一定也为 $n$ 的因数，所以枚举 $i$ 和枚举 $\frac n i$ 是等价的，如图，在 $5$ 之前所有数都能找到与之对应的数，所以我们枚举到 $5$ 即可，那么 $5$ 是怎么来的呢？很明显是 $\sqrt{n}$ 呐，因为这种数对的临界就是 $i$ 和 $i$ (当 $i^2=n$ 时)
在这里插入图片描述

bool check(int n){ if(n<2) return false; for(int i=2;i<sqrt(n);i++){ if(n%2==0) return false; } return true; }

但这些依然不够，有时我们需要得出一整段数中的质数，当然可以用上面的方法对这些数一个一个的判断，但这样太慢了，这时就要用到素数筛了

怎么筛素数

1.埃筛

埃筛的核心思想是一个合数一定是一个质数的倍数(是个人都知道)，所以我们只需枚举每一个质数，然后用它的倍数筛掉合数，但是我们需要枚举质数，可是我们埃筛就是为了得到质数，那怎么办？

首先我们知道，当我们枚举到一个数时，这个数要么被筛过了，要么还没被筛，那么没筛的是否就是质数呢？答案是肯定的，因为根据质数的定义，“除了1和它自身外，不能被其他自然数整除的数叫做质数”，换句话讲，一个质数的因数只有1和他本身，所以他还没被筛的话，就一定是质数了

void get_prime(int n){ memset(isprime,1,sizeof(isprime)); isprime[1]=0; for(int i=2;i<=n;i++){ if(isprime[i]==1){ for(int j=i*i;j<=n;j+=i){ isprime[j]=0; } } } }

2.线性筛

刚才的筛法会重复筛掉一些，如质数2会筛6，而3也会筛6，这就慢了许多，那么我们可不可以只筛一次呢，办法是有的，~~但不告诉你~~，就是只筛这个合数的最小质因数

做法

依次枚举每一个数
若当前数没被筛，则把这个数加入质数集合
对于每一个数，枚举当前已知质数，并相应筛掉 $当前数 \times 枚举到的质数$ ，而被筛掉的那个数的最小质因数一定是枚举到的质数(为什么看后面)
如果 $i$ 是枚举到的质数的倍数，停止枚举质数

先看代码理解做法

bool isprime[MAXN]; int prime[MAXN]; int cnt=0; void get_prime(int n){ memset(isprime,1,sizeof(isprime)); isprime[1]=0; for(int i=2;i<=n;i++){ if(isprime[i]==1){ prime[++cnt]=i; } for(int j=1;j<=cnt && i*prime[j]<=n;j++){ isprime[i*prime[j]]=0; if(i%prime[j]==0) break; } } } //最终的prime就保存了n以内的所有质数

原理

if(i%prime[j]==0) break;

这段程序保证了筛掉的那个数的最小质因数一定是prime[j]

理由:

$i$ 的最小质因数肯定是 $prime[j]$ 。
我们假设 $i$ 的最小质因数是 $prime[k]$
则：
若 $k<j$ 则在 $k$ 时就会break,而不会到 $j$ 再break,矛盾
若 $k>j$
$\because$ 我们是从小到大枚举质数
$\therefore$ $prime[k]>prime[j]$ ,即 $prime[k]$ 一定不是最小质因数，矛盾
综上， $i$ 的最小质因数肯定是 $prime[j]$
$i×prime[k](k>j)$ 的最小质因数一定是 $prime[j]$ 。
因为 $i$ 的最小质因数是 $prime[j]$ ，所以 $i×prime[k](k>j)$ 也含有 $Prime[j]$ 这个因数（这是 $i$ 的功劳），所以其最小质因数也是 $prime[j]$

第一条说明了： $i$ 的最小质因数是 $prime[j]$ ，那么 $i×prime[j]$ 的最小质因数也是 $prime[j]$ 。所以， $j$ 一定可以保证了筛掉的那个数的最小质因数是 $prime[j]$

第二条说明了：如果到j后不break，那么继续筛下去会不用最小质因数筛数，是无用的

一个作者进入过的误区：
当 $i$ 还不大的时候，可能会一层内就筛去大量合数，看上去耗时比较大
但是，由于保证了筛去的合数日后将不会再被筛（总共只筛一次），复杂度是线性的。到 $i$ 接近 $n$ 时，你会发现每层几乎都不用做什么事。

最后，希望大家不要因为它快就忘记它原本的名字，它叫欧拉筛

本文地址：https://blog.csdn.net/tanfuwen_/article/details/107886138

您可能感兴趣的文章:

如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！

质数怎么判断（线性筛查质数）

2020年08月10日 | 移动技术网IT编程 | 我要评论

目录