题解 | #筛选法求素数#

#include <stdio.h>
#include <stdlib.h>

int main() {
    unsigned short len = 0;
    unsigned short *parray = NULL;
    unsigned short count = 0;           // 统计0的个数

    // 多组输入
    while (EOF != scanf("%hu", &len)) {
        if (len < 2)
            return -1;

        // 动态申请内存
        parray = (unsigned short *)calloc(len - 1, sizeof(unsigned short));
        if (NULL == parray)
            return -1;
        
        // 将2~n之间的正整数放在数组内存储
        for (unsigned short i = 0; i < len - 1; i++) {
            parray[i] = i + 2;          // 下标为0的时候写的存储的是2，然后依次递增1
        }

        // 将数组中2之后的所有能被2整除的数清0，再将3之后的所有能被3整除的数清0 ，以此类推，直到n为止
        for (int i = 1; i < len - 1; i++) {         // 不包含2
            for (int j = i; j < len - 1; j++) {
                // 判断是不是素数
                if (0 == parray[j] % (i + 1))
                    parray[j] = 0;
            }
        }

        // 输出素数
        for (int i = 0; i < len - 1; i++) {
            // 数组中不为0 的数即为素数
            if (0 != parray[i])
                printf("%hu ", parray[i]);
            else        // 统计数组中2之后被清0 的个数
                count++;
        }

        // 换行+输出输出数组中2之后被清0 的个数
        printf("\n%hu\n", count);

        // 释放内存
        free(parray);
        parray = NULL;
    }

    return 0;
}