基本方法如下：
先列出从2~N的全体自然数，其中，2 是素数，在该数列中将2及其倍数去掉；
接下来数列中最小的3是素数，再将数列中的3及其倍数去掉；
接下来数列中最小的5是素数，…，重复该过程，直到数列为空。
每次从数列中取出的最小数构成不超过N的全体素数。

#include<stdio.h>
#include<stdlib.h>
#define N 20
int main()
{
    int a[N];
    int b[N];
    int i=2;
    int p=0;
    for(i=2;i<N;i++)
    {
        a[i]=i;
    }
    for(i=2;i<N;i++)
    {
        if(0!=a[i])
        {
         p=a[i];
         b[i]=a[i];
         for(i=2;i<N;i++)
         {
                if(!i%p)
                a[i]=0;
                }
            }
    }
    printf("N=%d  不大于N的素数为：\n",N);
    for(i=2;i<N;i++)
    {
        if(b[i])
        printf("%d.\n",b[i]);
        }
        system("pause");
        return 0;
    }
        
        
        
        
        

#include <stdio.h>
#define N 100

int primes[N];

int isArrayEmpty(int a[])
{
    int i=0;

    for(;i<N;++i)
    {
        if(a[i]!=0)  return 0;
    }

    return 1;
}

void processArray(int a[],int index)
{
    int i=0,min=0;

    for(;i<N;++i)
    {
        if(a[i]!=0)
        {
            min=a[i];
            primes[index]=min;
            break;
        }
    }

    for(i=0;i<N;++i)
    {
        if(a[i]%min==0)  a[i]=0;
    }
}

int main()
{
    int i=0,nums[N],j=0;
    for(;i<N;++i)
    {
        primes[i]=0;
        nums[i]=i+2;  //2....N+1
    }
    nums[N-1]=2;  //skip the last N+1

    while(!isArrayEmpty(nums))
    {
        processArray(nums,j);
        j++;
    }

    for(i=0;i<j;++i)
    {
        printf("%d ",primes[i]);
    }

    return 0;
}

[此贴子已经被作者于2016-4-23 16:02编辑过]

#include<stdio.h>
#define N 20

int main()
{
    int i, j, a[N];

    for(i=0; i<N; i++)
    {
        a[i] = i+2;
    }
    
    i = 0;
    while(a[i])
    {
        for(j=i+1; j<N; j++)   
        {
            if(!a[j])
            {
                continue;
            }
            
            if(!(a[j]%a[i]))
            {
                a[j] = 0;
            }
            else
            {
                if(!a[i+1])
                {
                    a[i+1] = a[j];
                }
            }
        }
        i++;
    }
    
    i = 0;
    while(a[i])
    {
        printf("%d\n", a[i]);
        i++;
    }

    return 0;
}

[此贴子已经被作者于2016-4-23 21:28编辑过]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define n 1000


 main()
{
    int i,j,k,*q;
    char *p;
   
    if(n<2) return 0;
    p=(char*)malloc((n+1)*sizeof(char));
    
    memset(p,0,(n+1)*sizeof(char));
    k=0;
    for(i=2;i<=n;i++)
    {
        if(!p[i])
        {
            for(j=i+i;j<=n;j+=i)p[j]=1;
            k++;
        }
    }
    
    printf("共查到%d个素数\n",k);
    
    q=(int*)malloc(k*sizeof(int));
    
    j=0;
       
    for(i=2;i<=n;i++)
    {
        if(!p[i])
        {
            
            q[j]=i;
            j++;
        } 
    }
    free(p);
    
    for(i=0;i<k;i++) printf("%d\n",q[i]);
    
    free(q);
    
    return 0;
}