欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

质数怎么判断(线性筛查质数)

程序员文章站 2022-06-19 16:19:54
各种判断质数的方法及筛法 线性筛的原理...



什么是质数

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

怎么判断质数

1.暴力判断

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

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.优化的暴力枚举

考虑到如果一个数iinn的因数,则ni\frac{n}{i}一定也为nn的因数,所以枚举ii和枚举ni\frac n i是等价的,如图,在55之前所有数都能找到与之对应的数,所以我们枚举到55即可,那么55是怎么来的呢?很明显是n\sqrt{n}呐,因为这种数对的临界就是iiii(当i2=ni^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,这就慢了许多,那么我们可不可以只筛一次呢,办法是有的,但不告诉你,就是只筛这个合数的最小质因数

做法

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

先看代码理解做法

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]

理由:

  • ii的最小质因数肯定是prime[j]prime[j]
    我们假设ii的最小质因数是prime[k]prime[k]
    则:
    k<jk<j 则在kk时就会break,而不会到jj再break,矛盾
    k>jk>j
    \because 我们是从小到大枚举质数
    \therefore prime[k]>prime[j]prime[k]>prime[j],即prime[k]prime[k]一定不是最小质因数,矛盾
    综上, ii的最小质因数肯定是prime[j]prime[j]

  • i×prime[k](k>j)i×prime[k](k>j)的最小质因数一定是prime[j]prime[j]
    因为ii的最小质因数是prime[j]prime[j],所以i×prime[k](k>j)i×prime[k](k>j)也含有 Prime[j]Prime[j]这个因数(这是ii的功劳),所以其最小质因数也是 prime[j]prime[j]

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

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

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

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

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

相关标签: 线性