筛选法求素数

 

int vis[1000]; //记录标记 
int p[1000]; //存素数 
int main()  
{  
	int n,i,j,k;
	int tot=0;
	memset(vis,0,sizeof vis);
	scanf("%d",&n);
    for(i=2;i<=n;i++)  
    {  
        if(vis[i]==0)  
        {  
            p[tot++]=i;  
        }  
        for(j=0;(j<tot)&&(i*p[j]<=n);j++) //筛选循环  
        {  
            vis[i*p[j]]=1;  
            if (i%p[j]==0) break;  
        }  
    }  
    printf("tot: %d\n",tot);
    for(i=0;i<tot;i++)  
    {  
        printf("%d\n",p[i]);  
    }    
}