目录
什么是质数
数学家们希望用乘法表示所有的正整数
这时候,他们发现,有一些数字(假定为 (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;
}
这样就完成了