素数

#include <cstdio>
#include <cmath>
#include <cstring>
const int MAXN = 1e8 + 5; 
bool prime[MAXN];//true表示合数，false表示素数 
bool flag[MAXN];//标记数字是否为已经找出的素数的倍数，true表示是， false表示不是
int Prime[MAXN];//用于存储欧拉筛法的素数 
int tot;//欧拉筛法素数的个数 
int ans[MAXN];//存储区间素数 
bool Prime1(int x) {//朴素算法 
    if (x < 2) {
        return false;
    }
    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

void Prime2(int x) {//埃式筛法 
    for (int i = 2; i <= x; i++) {
        if (!prime[i]) {
            for (int j = i * i; j <= x; j += i) {
                prime[j] = true;
            }
        }
    }
    prime[1] = true;
}

int Prime3(int x) {//欧拉筛法(线性筛法) 
    for (int i = 2; i <= x; i++) {
        if (flag[i] == false) {//不是素数的倍数，则一定是素数，存储 
            Prime[++tot] = i; 
        }
        for (int j = 1; j <= tot && i * Prime[j] <= x; j++) {//保证每一个合数是被他的最小质因子标记出来 
            flag[i * Prime[j]] =  true; 
            if (i % Prime[j] == 0) {//避免重复运算 
                break;
            }
        }
    }
    return tot;
} 

int Prime4(int a, int b) {//区间素数筛法 
    if (a < 2) a = 2;
    int t = sqrt(b), tot = 0;
    int cnt = Prime3(t);//得到2 ~ sqrt(b)的所有素数 
    memset(flag, false, sizeof(flag));
    for (int i = 1; i <= cnt; i++) {//枚举2 ~ sqrt(b)的所有素数 
        int l = a / Prime[i], r = b / Prime[i];//确定枚举倍数 
        if (l <= 1) {
            l = 2;
        }
        for (int j = l; j <= r; j++) {//将已经得到的素数的倍数标记为合数 
            flag[Prime[i] * j - a] = true; 
        }
    }
    for (int i = 0; i <= b - a; i++) {
        if (flag[i] == false) {
            ans[++tot] = i + a;
        }
    }
    return tot;
} 
int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    int t = Prime4(a, b); 
    for (int i = 1; i <= t; i++) {
        printf("%d ", ans[i]);
    }
    return 0;
}