题解 | #筛选法求素数#

#include <stdio.h>
#include <math.h> 

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        int *laker = (int *)malloc(n * sizeof(int)); // 动态分配数组
        if (laker == NULL) {
            return 1; // 如果内存分配失败，返回错误
        }
        int count = 0; // 用于计数素数的数量

        for (int i = 0; i < n; i++) {
            laker[i] = i + 1;
        }

        for (int i = 0; i < n; i++) {
            if (laker[i] > 1) { // 1不是素数，所以从2开始检查
                int isPrime = 1; // 假设当前数是素数
                for (int j = 2; j <= sqrt(laker[i]); j++) {
                    if (laker[i] % j == 0) {
                        isPrime = 0; // 如果能被整除，则不是素数
                        break;
                    }
                }
                if (isPrime) {
                    printf("%d ", laker[i]); // 打印素数，并添加空格分隔
                    count++;
                }
            }
        }
        
        printf("\n"); // 打印换行
        printf("%d",n-1-count);
        free(laker); // 释放动态分配的内存
    }
    return 0;
}