质数是针对于>1的自然数来定义的,对<=1的整数既不是质数也不是合数
判断两个条件:是否大于1和是否约数只有1和它本身(约数:a/b=c,c为整数,则b为a的约数)
优化:
若d能整除n,则n/d也能整除n,所以可以从时间复杂度n降到根号n
质因数是每个合数都可以写成几个质数相乘的形式,这些质数就是合数的质因数
#include<bits/stdc++.h>
using namespace std;
const int N=110;
bool prime(int n)
{
if(n<2)return false;//如果小于2则肯定不是素数,因为素数是针对于大于1的数而言的
for(int i=2;i<=n/i;i++)//推荐写法:i<=n/i,即i<=根号n
{
if(n%i==0)//如果有其它约数
return false;
}
return true;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int a;
scanf("%d",&a);
if(prime(a))puts("Yes");
else
puts("No");
}
return 0;
}