题解 | 筛出一定范围内所有素数

//主要难点:利用筛法找素数(initial)
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 1e5 + 10;
bool isprime[maxn];
vector<int>prime;
void initial() {
    for (int i = 0; i < maxn; i++) { //初始化
        isprime[i] = true;           //假设全部是质数
    }
    isprime[0] = false;              //已知0,1不是质数
    isprime[1] = false;
    for (int i = 2; i < maxn; i++) {
        if (!isprime[i]) {          //不是质素跳过
            continue;
        }
        prime.push_back(i);        //是质数加入数组
        for (int j = i * i; j < maxn;
                j += i) {    //。当判定i为素数，要标记其倍数为非素数时，并未从2*i开始标记，而是直接从i*i开始标记的
            isprime[j] =
                false;  //原因很明显：i*k（k<i）必定已经在求得k的某个素因数（必定小于i）时被标记过，即i*k同时也是k的素因数的倍数
        }
    }
}

// int numberofprimefactor(int number) {     //求质因子个数
//  int answer = 0;                          //记录答案质因子个数
//  for (int i = 0; i < prime.size(); i++) {
//      int factor = prime[i];
//      if (number < factor) {
//          break;                            //循环退出条件
//      }
//      int exponent = 0;
//      while (number % factor == 0) {
//          exponent++;                        //当前质因子对应指数
//          number /= factor;
//      }
//      answer += exponent;                     //答案为各质因子指数和
//  }
//if (number > 1) {
//		answer += 1;
//	}
//  return answer;
// }


int main() {

    initial();//shai fa

    int n;
    while (scanf("%d", &n) != EOF) {
        bool isprint = false;
        for (int i = 0; i < prime.size()&&prime[i]<n; i++) {
            if (  prime[i] % 10 == 1) {
                isprint = true;
                printf("%d ", prime[i]);
            }
        }
        if (!isprint) {
            printf("-1");
        }
        printf("\n");
    }
    return 0;
}
// int k;                                      //第个质数
// while (scanf("%d", &k) != EOF) {
//     printf("%d\n", prime[k - 1]);
// }
// int number;                                //求质因子个数
// while (scanf("%d", &number) != EOF) {
//  printf("%d\n", numberofprimefactor(number));
// }