【数论】 质数知识总结(质数判断、筛选、质因子分解、互质)

  • Post author:
  • Post category:其他




一.定义

质数,又称素数,若一个正整数无法被除了1和它自身以外的其它数整除,则称其为质数,否则为合数。特殊地,1既不是合数也不是质数



二.质数的判断


试除法:

检查所有可能成为n的因子的数,若没有找到因子,则证明这个数是一个质数

一种朴素的做法就是从2遍历到N-1观察有无N的因子,若没有则说明N为质数,依据的想法是N的因子必然在1~N的范围内


改进:

其实我们只要找到一个N的因子(除了1和它本身)就可以证明N是个合数。

定理:如果N是一个合数,则必然存在一个N的因子T,满足



2

T

N

2≤T≤√N






2













T
















N






证明:反证法即可

因此我们只需要从2遍历到√N即可,时间复杂度缩小为O(√N)


其它的想法:


素数筛进行预处理,用prime数组存放所有素数,然后从



p

r

i

m

e

[

1

]

prime[1]






p


r


i


m


e


[


1


]





遍历到



p

r

i

m

e

[

i

]

p

r

i

m

e

[

i

]

N

prime[i]*prime[i]≤N






p


r


i


m


e


[


i


]













p


r


i


m


e


[


i


]













N





,因为N如果是合数,则必然存在小于等于√N的素数因子

证明:前文以经证明过必然存在小于√N的因子,如果这个因子是素数自不必说,如果是合数,那么合数可以被分解为素因子的乘积。

目的:可以进一步减少时间复杂度,需要遍历的数更少了(因为素数的分布相对稀疏,10万以内的素数只有9500多个)

当然这只是我个人的想法,没有仔细的验证与思考,并且大部分时候O(√N)的复杂度就已经很优秀了



三.质数的筛选

筛选:即从1~N中筛选出所有的质数


思路

:一个数x的倍数——2x,3x,4x……必然不是素数


具体做法

:从2开始扫描所有的数x,并将x的所有倍数标记为合数。如果扫描到一个数y,发现y没被标记过,说明y一定是素数,因为2~y-1没有y的因子,符合素数定义

因为每个合数必然有质因子,所以只让素数来进行标记的工作以减少重复标记,比如27让3来标记为合数即可。

这就是埃氏筛

缺点:有些数仍会被重复标记,比如12既是3的倍数又是2的倍数


改进:

线性筛/欧拉筛:

即找到一个数的唯一产生方式:让一个数的

最小质因子

对其进行标记,比如12,虽然有2,3两个质因子,但只让2来标记12。

时间复杂度接近



O

(

N

)

O(N)






O


(


N


)





,所以称为线性筛


实现:

int Prime[100005];
bool Isprime[100005];
int cnt=1;

void Prime_excel(){
  for(int i=2;i<=100000;i++) Isprime[i]=1;
  for(int i=2;i<=100000;i++){
    if(Isprime[i]) Prime[cnt++]=i;
    for(int j=1;j<cnt&&Prime[j]*i<=100000;j++){
        Isprime[Prime[j]*i]=0;
        if(i%Prime[j]==0)
            break;
    }
  }
}

对于

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

的解释:

线性筛的思想是只让

最小质因子

对合数进行标记,也就是:

Isprime[Prime[j]*i]=0;

这句话,这里Prime[j]即最小质因子。

如果

i%Prime[j]==0

,不妨将i表示为k*Prime[j],如果令j++继续筛下去的话,下一个要筛的数是

Prime[j+1]*i

,显然这个数的最小质因子应该是Prime[j]而不是Prime[j+1],违背了线性筛的思想,所以需要break



四.质因子分解


算术基本定理:

任何一个大于1的正整数都可以被分解为质因子的幂次的积





N

=

P

1

a

1

P

2

a

2

P

3

a

3

P

m

a

m

N=P_1^{a_1}\cdot P_2^{a_2}\cdot P_3^{a_3}\cdot\cdot\cdot P_m^{a_m}






N




=









P










1










a










1















































P










2










a










2















































P










3










a










3





























































P










m










a










m





































这个定理看似非常简单,但是在很多地方都会应用到,要有将一个数分解为质因子幂次乘积的思想


分解质因子:

int factor[100];
int cnt=0;

void divide(int N){
    cnt=0;
    for(int i=2;i*i<=N;i++){
       if(N%i==0){
         factor[cnt++]=i;
         while(N%i==0)
            N/=i;
       }
    }
    if(N>1)  factor[cnt++]=N; //质数在根号N内没有因子,故可能没除完
}

如果还想知道每个质因子的幂次再用一个数组存就行



五.互质

最大公约数:great common divisor,简称gcd

互质定义:若gcd(a,b)=1,则称a与b互质

关于欧几里得算法求gcd的证明:

欧几里得算法证明


欧拉函数:

在数论中,对正整数n,欧拉函数是小于或等于n的正整数中与n互质的数的数目(因此φ(1)=1)。此函数以其首名研究者欧拉命名(Euler’s totient function),它又称为Euler’s totient function、φ函数、欧拉商数等。 例如φ(8)=4,因为1,3,5,7均和8互质。

具体信息可见:

欧拉函数计算及打表



版权声明:本文为Qiuker_jl原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。