#include
#include
void main()
{
int m,i,k;
scanf("%d",&m);
k=sqrt(m); //一个数不是素数，那么开平方也一定不是素数。
//将一个数开平方再取整，可以减少比较次数，提高运行效率。
for(i=2;i<=k;i++)//一个一个比较看这个数能不能除尽小于它的所有数
if(m%i==0) //如果可以除尽这个数，那么就跳出循环
break;
if(i>=k+1) //如果i>=k+1 说明一直循环到最后了，中间没有可以除尽的数，这个数就是素数
printf("%d is a prime number\n",m);
else //相反就不是素数
printf("%d is not a prime number\n",m);
system("pause");
}
