质数：质数（prime number）又称，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他，这样的数称为质数。

　　题设：输入一个大于1的自然数，求出从2到该数之间所有的质数。

　　1.　　按照素数的定义来求取，用两个for循环。

1 #include 
     
       2 int prime(int i){ 3     int j; 4     for(j=2;j
     

　　2.　　对 1 进行优化，先排除可以被2整除的数（一定不是质数），sqrt（）减少循环的区间。

1 #include 
     
       2 #include 
      
        3 int prime(int i){ 4     int j,temp; 5     temp=sqrt(i)+1;//sqrt() 6     for(j=2;j
      
     

　　3.　　筛选法

1 #include "stdio.h" 2 #include "math.h" 3 int main(void){ 4     int i,j,n,t,a[10000]; 5     t = 0; 6     for(i = 0; i < 10000; i++){ 7         a[i] = 1; 8     } 9 10     printf("请输入一个大于1的整数: ");11     scanf("%d",&n);12 13     for(i = 2; i <= n; i++){14         if(a[i] == 1){15             for(j = i*2; j <= n; j = j+i){16                 a[j] = 0;17             }18             printf("%d ",i);19             t++;20         }21     }22     printf("\n");23     printf("%d",t);24 25 26 }

 　　3-1　　筛选法优化

1 #include 
     
       2 #include 
      
        3  4 int main(){ 5     int arr[1000], i, j, n; 6     arr[2] = 1; 7     for(i=3; i<1000; i++){ 8         if(i % 2==0){ 9             arr[i] = 0;10         }else{11             arr[i] = 1;12         }13     }14 15     printf("请输入一个整数： ");16     scanf( "%d", &n);17 18     for(i=2; i<=n; i++){19         if (arr[i] == 1){20             for(j=i*i; j<=n; j=j+i*2){21                 arr[j] = 0;22             }23 24             printf("%d  ",i);25         }26     27     }28 29 30 }