本文共 1635 字，大约阅读时间需要 5 分钟。

步骤简介

• 初始化数组a，使得a[i] = i;
• 对i = 2，3，4，…，sqrt（N）分别做：“筛掉a中所有的a[i]的倍数”
  • 对数组a中a[i]后面的所有的数a[j]分别做：若“a[j]是a[i]的倍数”，则"筛掉a[j]"
• 输出数组中余下的a[i]!= 0的数

我的代码

#include 
   
    #include 
    
     #include 
     
      int main(){
       //筛法求100以内的素数    int a[100],i = 0,n = 100,edge,j;    //初始化所有的数组元素    for(;i < 100;i ++)    {
           a[i] = i;    }    //做筛法的准备：求出对应的开方数，新得遍历倍数    edge = (int)sqrt(n);    for(i = 2;i <= edge;i ++)    {
           for(j = 2;j < n / 2;j ++)        {
               if(j * i < n)            {
                   a[j * i] = 0;            }        }    }    //输出所有的不为零的部分    for(i = 0;i < n;i ++)    {
           if(a[i] != 0)        {
               printf("%d  \n",a[i]);        }    }    return 0;}
     
    
   

教程代码

#include 
   
    #include 
    
     #include 
     
      #define N 100void PrintPrime(int a[], int n);void SiftPrime(int a[], int n);int main(){
       int a[N+1];    SiftPrime(a,N);    PrintPrime(a,N);    return 0;}void SiftPrime(int a[], int n){
       int i ,j ,edge;    for(i = 2; i <= N; i ++)    {
           a[i] = i;    }    edge = sqrt(N);    for(i = 2;i <= edge;i ++)    {
           for(j = i + 1;j <= N;j ++)        {
               if(a[i] != 0 && a[j] != 0 && a[j] % a[i] == 0)            {
                   a[j] = 0;            }        }    }}void PrintPrime(int a[],int n){
       int i ;    for(i = 2;i <= N;i ++)    {
           if(a[i] != 0)        {
               printf("%d \t",a[i]);        }    }    printf("\n");}
     
    
   

分析与总结

• 判定是否是某数的倍数，不一定是乘法，也可以是除法。乘法需要考虑是否越界，但是除法只需要将剩下所有的逐一遍历即可
• 大循环确定其为某个数的倍数，该数之前一定没有任何数的倍数，仅在其后才有相关的倍数。
• 没有理清两个数的因数的关系，一定是一个大，一个数小，大的数一定小于N / 2，所以没有必要全部都遍历。

转载地址：http://iggpb.baihongyu.com/