爱拉托斯散筛法求出100以内的全部素数（)

爱拉托斯散筛法求出100以内的全部素数（)

求100以及以内的素数：
1.求【√100】=10；
2.求10及以内的素数：2、3、5、7
3.从1-100中依次删除2、3、5、7的倍数。
删除方式(从每个数的平方删起)
对于2：依次删除2^2（即2×2）、2 × 3、…、2 ×50；
对于3：依次删除3^2（即3×3）、3 × 5、…、3 × 33；
对于5：依次删除5^2（即5×5) 、5 × 7、…、5×19；
对于7：依次删除7^2（即7×7）、7×11、7×13。
注意：因为2、3、5、7的倍数会有重叠的，所以在之前已经删除过的数字就不必再次删除了。

c语言代码：

#include<stdio.h>
#include<math.h>
void findp(int part[])//寻找不大于根号100的素数 
{int num,i;for(num=2;num<=sqrt(100);++num){for(i=2;i<=num-1;++i){if(num%i==0)break;}if(i<num) part[num]=0;else part[num]=1;}printf("n小于等于根号100的所有素数为："); for(i=2;i<=22;++i){if(part[i]==1)printf("%d  ",i);}printf("nn"); } 
void delete(int all[],int part[])//逐个删除不大于根号100的素数的倍数并打印删除的数字，打印最后的100以内的素数 
{int i,j;for(i=2;i<=10;++i){if(part[i]==1){printf("对于素数%d删除其倍数：n",i); for(j=i;i*j<=100;++j){if(all[i*j]==1) continue; elseall[i*j]=1;//删除倍数printf("%dt",i*j);}}printf("nn"); }printf("100以内的所有素数为：n"); int count=0;for(i=2;i<=100;++i){if(all[i]==0){printf("%dt",i);++count;}}printf("nn-----100以内的素数共有< %d >个-------hao",count); printf("n"); }
int main()
{printf("----------< 爱拉托斯散筛法求出100以内的全部素数 >-----------n");int a[100]={0};int p[10]={0};//sqrt(100)=10findp(p) ;delete(a,p);return 0;
}

结果：

----------< 爱拉托斯散筛法求出100以内的全部素数 >-----------小于等于根号100的所有素数为：2  3  5  7对于素数2删除其倍数：
4       6       8       10      12      14      16      18      20      22      24      26      28      30      3234      36      38      40      42      44      46      48      50      52      54      56      58      6062      64      66      68      70      72      74      76      78      80      82      84      86      8890      92      94      96      98      100对于素数3删除其倍数：
9       15      21      27      33      39      45      51      57      63      69      75      81      87      9399对于素数5删除其倍数：
25      35      55      65      85      95对于素数7删除其倍数：
49      77      91100以内的所有素数为：
2       3       5       7       11      13      17      19      23      29      31      37      41      43      4753      59      61      67      71      73      79      83      89      97-----100以内的素数共有< 25 >个-------hao