素数

埃氏筛法
欧拉筛法：https://blog.csdn.net/Losk_0/article/details/87884390

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 10010;
vector<int> prime;
//如果i为素数，则IsPrime[i]为false;否则，IsPrime[i]为true
bool IsPrime[maxn];
int num = 0;
// 埃氏筛法
void Find_Prime1()
{
    memset(IsPrime, true, sizeof(IsPrime));
    for (int i = 2; i < maxn; i++)
    {
        if (IsPrime[i]) //如果i为素数
        {
            if (i % 10 == 1)
            {
                prime.push_back(i);
            }
            for (int j = i * i; j < maxn; j += i)
            {
                IsPrime[j] = false;
            }
        }
    }
}
// 欧拉筛法
void Find_Prime2(){
    for(int i = 2; i < maxn; i++){
        if(!IsPrime[i]){
            prime.push_back(i);
        }
        for(int j = 0; j < prime.size() && i * prime[j] < maxn; j++){
            IsPrime[i * prime[j]] = true;
            if(i % prime[j] == 0){
                break;
            }
        }
    }
}
int main()
{
    int n;
    Find_Prime1();
    while (~scanf("%d", &n))
    {
        //从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字
        int pos = lower_bound(prime.begin(), prime.end(), n) - prime.begin();
        if (pos == 0)
        {
            printf("-1");
            continue;
        }
        for (int i = 0; i < pos; i++)
        {
            i == 0 ? printf("%d", prime[i]) : printf(" %d", prime[i]);
        }
    }
    return 0;
}