题解 | #素数#

#include <stdio.h>
#include <math.h>
#include <stdbool.h>
// 判断质数：
bool Prime(int x) {
    if (x == 1)
        return false;
    int y = sqrt(x);
    for (int i = 2; i <= y; i++) {
        if (x % i == 0)
            return false;
    }
    return true;
}
typedef struct {
    int data;
    bool p;
    int cmp;
} DataP;
int main() {
    int n;
    scanf("%d", &n);
    DataP D[n + 1];
    for (int i = 0; i < n + 1; i++) {
        D[i].data = i;
        D[i].cmp = 0;
    }
    D[0].p = 0;
    D[0].cmp = 1;
    D[1].p = 0;
    D[1].cmp = 1;
    for (int j = 2; j < n ; j++) {
        if (D[j].cmp == 0) {
            int k = j;
            if (Prime(D[k].data)) {
                D[k].p = 1;
                D[k].cmp = 1;
                while (k * k < n) {
                    k *= k;
                    D[k].p = 0;
                    D[k].cmp = 1;
                }
            } else {
                D[k].p = 0;
                D[k].cmp = 1;
                while (k * k < n) {
                    k *= k;
                    D[k].p = 0;
                    D[k].cmp = 1;
                }
            }
        } else
            continue;
    }
    for (int l = 0; l < n ; l++) {
        if (D[l].p && l % 10 == 1)
            printf("%d ", D[l].data);
        else
            continue;
    }
    printf("\n");
    return 0;
}