为什么判断质数可以用平方根优化
Cortius_D_LaSith
·
2023-11-11 14:30:44
·
个人记录
bool isprime(int x){
if(x<2)return 0;
for(i=2;i*i<=x;++i){
if(x%i==0)return 0;
}
return 1;
}
这是一个判断x是否为质数的函数，循环的条件是i*i<=x，也就是i小于等于x的平方根。
那么为什么判断质数可以用平方根优化呢
比如19是一个质数，从2到18寻找它的因子。
$i=2$：2不能被19整除，$\lfloor{\frac{19}{2}}\rfloor=8$，这样就能判断2和8都不是19的因子;
$i=3$：3不能被19整除，$\lfloor{\frac{19}{3}}\rfloor=6$，这样就能判断3和6都不是19的因子;
$i=4$：4不能被19整除，$\lfloor{\frac{19}{4}}\rfloor=4$，这样就能判断4不是19的因子;
$i=5$：5不能被19整除，$\lfloor{\frac{19}{5}}\rfloor=3$，在前面的循环中已经判断出3不是19的因子了。
$i=6$：6不能被19整除，$\lfloor{\frac{19}{6}}\rfloor=3$，在前面的循环中已经判断出3不是19的因子了。
$i=7$：7不能被19整除，$\lfloor{\frac{19}{7}}\rfloor=2$，在前面的循环中已经判断出2不是19的因子了。
$i=8$：8不能被19整除，$\lfloor{\frac{19}{8}}\rfloor=2$，在前面的循环中已经判断出2不是19的因子了。
$i=9$：9不能被19整除，$\lfloor{\frac{19}{9}}\rfloor=2$，在前面的循环中已经判断出2不是19的因子了。
$\lfloor\sqrt{19}\rfloor=4
对于所有小于等于4的数字x，如果x不是19的因子，则\lfloor\frac{19}{x}\rfloor也不是19的因子。
对于所有比4大的数字x，\lfloor\frac{19}{x}\rfloor的值都小于4，假设在i\in(4,19)中存在19的因子x，那么其充要条件是存在i\in(1,4]使得\lfloor\frac{19}{i}\rfloor=x并且i是19的因子。而在此之前所有小于等于4的数字都已经证明不是19的因子（也就是我们已经证伪了这个充要条件），所以
在i\in(4,19)中不存在19的因子x。
综上所述，对于一个大于1的正整数x，如果i\in(1,\lfloor\sqrt x\rfloor]不存在x的因子，则i\in(\lfloor\sqrt x\rfloor,x)也不存在x的因子。
因此，判断一个数字是不是质数，只要判断到它平方根之前是否有数字是它的因子即可。