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

Eratosthenes筛法

#include 
   
    #include 
    
     #include 
     
      //Eratosthenesconst int maxn = 10000000 + 5;const int maxp = 700000;int vis[maxn];int prime[maxp];void sieve(int n)  //screen out the prime numbers{    int m = sqrt(n + 0.5);    memset(vis, 0, sizeof(vis));    for(int i = 2; i <= m; i++)        if(!vis[i])            for(int j = i * i; j <= n; j += i)                vis[j] = 1;}int prime_numbers(int n){    sieve(n);    int c = 0;  //the number of prime numbers    for(int i = 2; i <= n; i++)        if(!vis[i])        {            prime[c] = i;            c++;        }    return c;}//the end of Eratosthenesint main(){    int t;    while(scanf("%d", &t) != EOF)    {        printf("total prime numbers: %d\n\n", prime_numbers(t));        for(int i = 0; i < prime_numbers(t); i++)            printf("%d\n", prime[i]);    }    return 0;}
     
    
   

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