已经停更 7 天了，各位久等了。
质数，是各位OIer们接触到的第一个数论知识。我们今天就来认识一下质数。
质数的定义
只有 1 与它本身两个因数的数叫做质数。
特别地， 1 不是质数。
质数的判定
使用循环枚举，若 i 能被 n 整除，则这个数不是质数。
从 2 开始枚举，但只用枚举到 \sqrt{n} 即可。因为因数是成对出现的，若 a 是 n 的因数，则 \dfrac{n}{a} 一定是 n 的因数。若不存在一个小于等于 \sqrt{n} 的非 1 非 n 因数 ，也就不存在大于 \dfrac{n}{\sqrt{n}}=\sqrt{n} 非 1 非 n 因数 ，故不存在非 1 非 n 因数。
i≤\sqrt{n} 可以写成 i\times i≤n （两侧同时平方）。
代码：
for(int i=2;i*i<=n;i++){
if(n%i==0){
isp=0;
break;
}
}
质数的搜寻
我们可以新建一个数组isp代表某个位置上的数是否为质数。
isp_i 代表 i 是否为质数。
假设 n 为质数，则 n 的倍数（不包括 n ）都不为质数。
可以写出代码：
for(int i=2;i*i<=n;i++){
if(!isp[i]){
for(int j=2*i;j<=n;j+=i){
isp[j]=1;
}
}
}
注意我这里的0代表质数，1代表非质数。
分解质因数
分解质因数可能对萌新来说比较难理解，看不懂的可以多看几遍。
分解质因数就是将 n 表示成 2^{a_1}\times 3^{a_2}\times 5^{a_3}\times ...\times p_i^{a_i} 的形式。
可以从 2 到 \sqrt{n} 枚举，若 i 能被 n 整除，则用 n 除以 i ，直到不能被 i 整除。
但是会有特殊情况，最后还留下一个大质数。
所以除到最后 n≠1 就要将 n 输出。
代码：
for(int i=2;i*i<=n;i++){
if(n%i==0){
n/=i;
cout<<i<<" ";
}
}
if(n!=1) cout<<n;
例题
例题三质数。
我们要知道，只有完全平方数有奇数个因数。
Why?
我们要先了解求因数个数的方法：
先将 n 分解质因数，得到 n=\Pi_{k=1}^m p_i^{a_i} 。
则 n 的因数个数为 \Pi_{i=1}^m a_i+1 。
可以尝试推一下，其实就是乘法原理。
那么我们要让 n 的因数个数为奇数，则对于每个 a_i+1 都为奇数。每个 a_i 都为偶数。
假设 a_i=2b_i 。
n=\Pi_{k=1}^m p_i^{2b_i}={(\Pi_{k=1}^m p_i^{b_i})}^2
不难发现， n 为完全平方数。
那么对于三质数，也就是 \Pi_{k=1}^m a_i+1=3 。
不难发现， m=1 即 \sqrt{n} 是个质数。
程序就不难写了，我这里就不贴了。
再给大家推一道题区间乘积。
这道题还是比较难的，大家可以先看看题解，多想一想。