题解 | #筛选法求素数#

#include <stdio.h>

int isPrime(int n) 
{
    if (n <= 1) 
    {
        return 0; // 不是素数
    }
    for (int i = 2; i * i <= n; i++) 
    {
        if (n % i == 0) 
        {
            return 0; // 不是素数
        }
    }
    return 1; // 是素数
}

int main() 
{
    int n = 0;
    while (scanf("%d", &n) != EOF)
    {
        int count = 0;
        int ret = 0;

        for (int i = 1; i <= n; i++)
        {
            if (isPrime(i))//设计一个函数判断是不是素数
            {
                printf("%d ", i);
                count++;//计算有多少个素数
            }
        }

        ret = n - 1 - count;//因为n里面多了一个1，所以把那个1减掉，再减去素数的个数就是我们去掉的数了
        printf("\n%d\n", ret);
    }

    return 0;
}