思路：
<1> 先将1挖掉(因为1不是素数)。
<2> 用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。
<3> 用3去除它后面的各数，把3的倍数挖掉。
<4> 分别用5…各数作为除数去除这些数以后的各数。 ——-《百度百科》
这样是素数都被筛选掉了，留下都不是素数。
这样是素数都被筛选掉了，留下都不是素数。
#include <stdio.h> #include <stdlib.h> #include <math.h> #include<time.h> int a[100000001]; //默认赋值为0 int main() { __int64 i,j,p,n; while (scanf("%I64d",&n)!=EOF&&n) { int count = 0; p = (int)sqrt(n*1.0); //因子加到根号n就可以了 a[0] = 1; a[1] = 1; //0和1不是素数,所以赋值1 for (i=2; i<=p; i++) //2~p作为除数筛选素数 { if (a[i]==0) { for (j=i*i; j<=n; j=j+i) //把2~p的倍数都赋值1表示不是素数 { a[j] = 1; } } } for (i=0; i<=n; i++) { if (a[i]==0) //留下的都是素数 count++; } printf("%d",count); printf("\n"); } return 0; }
上面代码的结果是输出素数个数，如果想输出全部素数，就直接输出a数组的下标即可