题解 | #筛选法求素数#

#include <stdio.h>
#include <math.h>
//将2~n之间的正整数放在数组内存储，将数组中2之后的所有能被2整除的数清0，再将3之后的所有能被3整除的数清0 ，以此类推，直到n为止。数组中不为0 的数即为素数。
int main()
{
    int n=0,arr[100]={0};
    while (scanf("%d", &n) != EOF)
    { 
        int i =0;
        //将2~n的数字存起来
        for(int i =2;i<=n;i++)
        {
            arr[i]=i;
        }
        //开始筛选
        
        for(i=2;i<=n;i++)
        {
            int j =0;
            for(j=2;j<i;j++)
            {
                if(i%j==0)//从2~i之间，如果出现了有一个数能整除i的话，那么这个数就不是素数，那么就将数组中的这个数重置为0，如果是素数的话就不管
                {
                    arr[i]=0;
                }
            }
        }
        int count=0;
        for(i=2;i<=n;i++)
        {
            if(arr[i]!=0)
            {
                printf("%d ",arr[i]);//如果这个数不是0，就将这个数打印出来，这个数就是素数
            }
            else 
            {
                count++;//输出数组中2之后被清0的数字的个数
            }
            

        }
        printf("\n%d\n",count);

        

    }
    return 0;
}