题解 | #素数#

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX_NUM = 10001;

/**
 * 保存素数
 */
vector<int> primeNum;

/**
 * 标记素数
 */
bool isPrimeNum[MAX_NUM];

/**
 * 初始化 isPrimeNum[]数组
 */
void init();

/**
 * 素数--北京航空航天大学
 * @return
 */
int main() {
    init();
    int n;
    while (cin >> n) {
        bool isOutput = false;
        for (int i = 1; i < n; ++i) {
            /*
             * i % 10 == 1表示个位为1，且i为素数，则输出
             */
            if (i % 10 == 1 && isPrimeNum[i]) {
                isOutput = true;
                cout << i << " ";
            }
        }
        if (!isOutput) {
            cout << "-1";
        }
        cout << endl;
    }

    return 0;
}

void init() {
    //初始化
    for (int i = 0; i < MAX_NUM; ++i) {
        isPrimeNum[i] = true;
    }
    /*
     * 0、1都不是素数
     */
    isPrimeNum[0] = false;
    isPrimeNum[1] = false;
    //从2开始遍历
    for (int i = 2; i < MAX_NUM; ++i) {
        if (!isPrimeNum[i]) {
            //数字i为非素数，则直接跳过
            continue;
        } else {
            //数字i为素数
            primeNum.push_back(i);
            /*
             * 若 i * i > MAX_NUM，则不用再循环了
             */
            if (i > MAX_NUM / i) {
                continue;
            }
            /*
             * 素数的整数倍为非素数
             * 直接从 i * i 开始循环，减少重复的工作，同时j += i，以保证j是i的整数倍
             * 为何从i*i开始呢？
             * 因为，i*k（其中k<i）必定已经在求k的某个素因数（必定小于i）时被标记过了，即i*k同时也是k的素因数的倍数。
             * 举例，标记素数3的倍数是，3 * 2 = 6，已经在标记素数2的倍数时被标记了，因此我们直接从3 * 3 = 9开始标记
             */
            for (int j = i * i; j < MAX_NUM; j += i) {
                isPrimeNum[j] = false;
            }
        }
    }
}