题解 | #素数#

#include<iostream>
#include<cstring>
using namespace std;

/*
* 找到一个素数，就将它的所有倍数均标记为非素数
* 遍历到一个数时
* 若未被任何小于它的素数标记为非素数，则确定其为素数
* 并标记它的所有倍数为非素数
* 继续遍历下一个数，直到遍历完
* 1不是素数
*/

int main() {
    //先把2~10000的所有素数都算一遍
    int tag[10005];     //标记数组
    int prime[10000];   //质数数组
    int cnt = 0;
    memset(tag, 0, sizeof(tag));
    for (int i = 2; i <= 10000; i++) {
        if (tag[i] == 0) { //还未被标记，是素数
            int bound = 10005 / i;
            for (int j = 2; j <= bound; j++) {
                tag[j * i] = 1;
            } //标记素数的倍数
            prime[cnt] = i;
            cnt++;
        }
    } //最后cnt得到的就是2~10000的素数总数

    //下面根据要求输出结果
    int n;
    while (scanf("%d", &n) != EOF) {
        int k = 0;
        int flag = 0;
        while (prime[k] < n) {
            if (prime[k] % 10 == 1 && prime[k] != 11) {
                printf(" %d", prime[k]);
            } else if (prime[k] == 11) {
                printf("%d", prime[k]);
                flag = 1;
            }
            k++;
        }
        if (!flag) {
            printf("-1");
        }
        printf("\n");
    }
}

预处理是类似问题的关键思想；不用每次都算一遍