质数

定义：又称素数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

质数判断的重要优化

我们知道，任何一个自然数$n$都可以写成两个自然数$a$和$b$的乘积：

我们把a和b叫做n的因数，并称小的那个是小因子，大的那个是大因子。

我们会发现小因子与大因子总是成对出现，即$b = n // a$。并且因子在变化过程中，分界线是n的平方根。越过了这条线，小因子就变成了对应的大因子。

因此，判断一个数$n$是否是质数，只需要判断它是否有不等于$1$的小因子，即$[2,\sqrt{n}]$之中是否存在能整除$n$的数。

代码模板

质数判断

1~20的所有质数