初等数论，一个整数不能整除他的平方数之内的整数就是素数。

程序如下：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 int main() 6 { 7     int prime(int); 8     int prime2(int); 9     int n;10     printf("input a number: ");11     scanf("%d",&n);12     if(prime2(n))13         printf("%d is a prime.\n",n);14     else printf("%d is not a prime.\n",n);15         system("pause");16     return 0;17 }18 int prime(int n){
   //普通法19     int flag=1,i;20     for(i=2;i