前置知识-因数和倍数 （六年级及以上自行跳过）：
\(
n\div m=k
\)，我们就说\(n\)是\(m\)和\(k\)的倍数，\(m\)和\(k\)是\(n\)的倍数。简单来说就是这样的：
\(\text{被除数}\div\text{除数,余数为0}\)，那我们就说除数是被除数的因数，被除数是除数的倍数。
前置知识-素数和合数 （六年级及以上自行跳过）
一个数的因数只有\(1\)和它本身，那这个数就是素数。
如：
\(2\)为素数，\(2\)的因数只有\(1\)和\(2\)。
\(4\)不是素数，他的因数有\(2\)。
自然数中（不包括负数，\(0\),\(1\)），不是素数就是合数。
注意：\(1\)不是素数，也不是合数。
本场主角-普通筛！
普通筛的思路：先特判\(1\)和\(2\)，再枚举\(2\sim n-1\)，如果\(n\)能整除\(i\)，那么\(n\)是合数，如果扫完都不能被整除，那么\(n\)为素数。
接下来放上JCer最爱——代码：
bool is_prime(int n){//判断素数的函数
if(n==1){//特判1
return 0;//1不是素数，返回0
}
if(n==2){//特判2
return 1;//2不是素数，返回1
}
for(int i=2;i<n;i++){//从2~n-1枚举
if(n%i==0){//如果能被整除
return 0;//不是素数，返回0
}
}
return 1;//是素数，返回1
}
不过这时间复杂度：\(O_{n}\)
面对数据范围很大的题目时……
所以，我们需要优化：
优化后的代码：
bool is_prime(int n){//判断素数的函数
if(n==1){//特判1
return 0;//1不是素数，返回0
}
if(n==2){//特判2
return 1;//2不是素数，返回1
}
for(int i=2;i*i<=n;i++){//枚举
if(n%i==0){//如果能被整除
return 0;//不是素数，返回0
}
}
return 1;//是素数，返回1
}
时间复杂度:\(O_{\sqrt n}\)
原理：
素数是因子为\(1\)和本身， 如果\(num\)不是素数，则还有其他因子，其中的因子，假如为\(a,b\).其中必有一个大于\(\sqrt{num}\) ，一个小于\(\sqrt{num}\) 。所以必有一个小于或等于其平方根的因数，那么验证素数时就只需要验证到其平方根就可以了。即一个合数一定含有小于它平方根的质因子。
有了模板之后，我们就开始愉快的水题时间吧！