题解 | #素数#

记录一下课本上讲的素数筛法

#include<stdio.h>
#include<string.h>
#define MAXN 10000

int prime[MAXN];
int isPrime[MAXN + 1]; //标记数组

//素数筛法初始化函数
void initial(int n) {
    //初始化isPrime数组，假设所有数都是素数
    memset(isPrime, 1, sizeof(isPrime));
    isPrime[0] = isPrime[1] = 0;
    int pCount = 0; //记录找到的素数数量
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            prime[pCount++] = i; //是素数将其添加到素数列表中
            //将素数的所有倍数标记为非素数
            for (int j = i * 2; j <= n; j += i) {
                isPrime[j] = 0;
            }
        }
    }
}

int main() {
    int n;
    initial(MAXN);
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; prime[i] < n; i++) {
            if ((prime[i] % 10) == 1) { //找个位为1的素数
                printf("%d ", prime[i]);
            }
        }
        printf("\n");
    }
    return 0;
}