题解 | #筛选法求素数#

#include<stdio.h>
int main(void)
{
    int n;
    while((scanf("%d",&n))!=EOF)
    {
        int *a=(int *)malloc(sizeof(int)*(n-1));//动态申请内存数组空间
        int count=0;
        for(int i=0;i<n-1;i++)//为数组赋值
            a[i]=i+2;
        for(int i=2;i<n-1;i++)//求素数，从第3个数组元素开始
        {
            for(int j=2;j<=a[i]/2;j++)//检测一个数能否被2-此数的一半整除，如果能则是非素数
                if(a[i]%j==0)//做好标记并计数
                {
                    a[i]=0;
                    count++;
                }
        }
        for(int i=0;i<n-1;i++)
            if(a[i]!=0)
            printf("%d ",a[i]);
        printf("\n%d",count);
    }
    return 0;
}