质数及其判法

时间:2022-06-10 23:05:18

目录

目录地址

什么是质数

数学家们希望用乘法表示所有的正整数

这时候,他们发现,有一些数字(假定为 (p) ),它们只能用 (1times p) 的形式表示(不考虑负因数),其它不能写成任何别的形式

对于这种数字,他们称呼为 质数 ,或称呼为 素数

而换句话说,它们只能分解为 (1) 乘上它本身;也就是说,它的因数只有 (1) 与它本身

这就是质数最重要的性质,也是它的定义

而对于其它的数字,我们称呼为 合数

合数的一些性质我们将会在后面的贴子中提到

质数的判法

对于一个数字 (n) 我们如何判定它是不是质数呢?

根据定义,我们很容易想到:枚举数字,查询是否只有 (1)(n) 是它的因数

而如果数字 (m) 是数字 (n) 的因数,很显然,存在数字 (k) 使得 (ktimes m=n)

反过来,我们可以写作 (ndiv m=kcdots0)

也就是说,如果 (m) 是数字 (n) 的因数, (n) 除以 (m) 的因数一定为 (0)

既然质数的因数只有 (1) 与它本身,那么其他数字除完的因数就一定不能为 (0)

根据数字的因数一定小于等于它本身,我们很快就可以写出程序(以 C 为例)

bool isprime=1;
for(int i=1;i<=n;i  ){
    if(n%i==0&&i!=1&&i!=n){
        isprime=0;
    }
}

当然,其实我们这样做的话,直接遍历的范围改成 (2)~((n-1)) 就行了

bool isprime=1;
for(int i=2;i<=n-1;i  ){
    if(n%i==0){
        isprime=0;
    }
}

这样一来,时间复杂度是 (O(n))

优化

时间复杂度能更快吗?

可以的

我们现在的思路是:枚举数字,查看 (n) 是否是合数

但我们想想,如果 (n) 是合数,那么它一定能写成 (n=mtimes k(m,kneq 1,n)) 的形式

我们直接假定 (mleq k)

那么,显然 (mleq sqrt{n})

这一步的证明我们可以用反证法:

(m>sqrt{n}) , 则 (ktimes mgeq mtimes m=m^2>(sqrt{n})^2=n) 就不是 (n)

所以 (mleq sqrt{n})

我们可以利用这个来优化我们的代码:我们修改上界,搜到 (sqrt n) 即可

bool isprime=1;
for(int i=2;i<=sqrt(n);i  ){
    if(n%i==0){
        isprime=0;
    }
}

当然,能不用 sqrt 函数我们尽量就不要用,毕竟它还需要支持实数的运算,跑得并不快

我们用 i*i<=n 来代替 i<=sqrt(n) 可以降低常数

bool isprime=1;
for(int i=2;i*i<=n;i  ){
    if(n%i==0){
        isprime=0;
    }
}

复杂度 (O(sqrt n))

当然,想优化常数还能再优化:判定完不是质数就可以直接退出了

bool isprime=1;
for(int i=2;i*i<=n;i  ){
    if(n%i==0){
        isprime=0;
        break;
    }
}

或者我们搞成内联函数的形式:

inline bool isprime(int n){
    for(int i=2;i*i<=n;i  ) if(n%i==0) return 0;
    return 1;
}

这样就完成了