质数怎么判断(线性筛查质数)
什么是质数
质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数。 —百度
怎么判断质数
1.暴力判断
直接枚举,如果是的因数,则一定是质数,如果找完都没找到这样的说明是合数,纯粹是根据定义来判断
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.优化的暴力枚举
考虑到如果一个数为的因数,则一定也为的因数,所以枚举和枚举是等价的,如图,在之前所有数都能找到与之对应的数,所以我们枚举到即可,那么是怎么来的呢?很明显是呐,因为这种数对的临界就是和(当时)
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,这就慢了许多,那么我们可不可以只筛一次呢,办法是有的,但不告诉你,就是只筛这个合数的最小质因数
做法
- 依次枚举每一个数
- 若当前数没被筛,则把这个数加入质数集合
- 对于每一个数,枚举当前已知质数,并相应筛掉,而被筛掉的那个数的最小质因数一定是枚举到的质数(为什么看后面)
- 如果是枚举到的质数的倍数,停止枚举质数
先看代码理解做法
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]
理由:
-
的最小质因数肯定是。
我们假设的最小质因数是
则:
若 则在时就会break,而不会到再break,矛盾
若
我们是从小到大枚举质数
,即一定不是最小质因数,矛盾
综上, 的最小质因数肯定是 -
的最小质因数一定是。
因为的最小质因数是,所以也含有 这个因数(这是的功劳),所以其最小质因数也是
第一条说明了:的最小质因数是,那么的最小质因数也是。所以,一定可以保证了筛掉的那个数的最小质因数是
第二条说明了:如果到j后不break,那么继续筛下去会不用最小质因数筛数,是无用的
一个作者进入过的误区:
当还不大的时候,可能会一层内就筛去大量合数,看上去耗时比较大
但是,由于保证了筛去的合数日后将不会再被筛(总共只筛一次),复杂度是线性的。到接近 时,你会发现每层几乎都不用做什么事。
最后,希望大家不要因为它快就忘记它原本的名字,它叫欧 拉 筛
本文地址:https://blog.csdn.net/tanfuwen_/article/details/107886138
上一篇: (*(工)*):目录