题解 | #筛选法求素数#

#include <stdio.h>
#include <stdlib.h>
// 根据输入的数字n构建从2开始的数组
int* Creatarr(int n) {
    int* arr = (int* )calloc(sizeof(int) * n, sizeof(int));
    for (int i = 0; i < n - 1; ++i) {
        arr[i] = i + 2;
    }
    return arr;
}
// 根据题意，将元素对2 3 4 ...取余，不是素数的项替换为零
int* Primernums(int* arr, int arrsize, int* returnSize) {
    int div = 2, j = 0;
    int* ret = (int* )calloc(sizeof(int) * arrsize, sizeof(int));
    while (div != arrsize + 2) {
        int isPrinums = 1;
        for (int i = div - 1; i < arrsize; ++i) {
            if (arr[i] % div == 0) {
                arr[i] = 0;
            }
        }
        ++div;
    }
    // 构建返回数组，去除为零的项
    for (int i = 0; i < arrsize; ++i) {
        if (arr[i] != 0) {
            ret[j] = arr[i];
            ++j;
        }
    }
    *returnSize = j;
    return ret;
}
int main() {
    int n, returnSize;
    while (scanf("%d", &n) != EOF) {
        int* arr = Creatarr(n);
        int* ans = Primernums(arr, n - 1, &returnSize);
        int* pans = ans;
        for (int i = 0; i < returnSize; ++i) {
            printf("%d ", *pans++);
        }
        printf("\n%d", n - 1 - returnSize);
        free(arr);
        arr = NULL;
        free(ans);
        ans = NULL;
    }
    return 0;
}