为什么欧筛比埃筛慢

埃筛：

#include <iostream>
#include <cstring>
#include <bitset>

const int N = 1e8 + 5;

int prime[N];
std::bitset <N> isPrime;

int main(){

    std::cin.tie(0)->sync_with_stdio(0);

    int n,q,cnt = 0;

    std::cin >> n >> q;
    isPrime.set();
    isPrime[0] = isPrime[1] = false;
    for (int i = 2;i * i <= n;i++)
        if (isPrime[i])
            for (int j = i * i;j <= n;j += i) 
                isPrime[j] = false;
    for (int i = 2;i <= n;i++)
        if (isPrime[i])
            prime[++cnt] = i;
    while (q--){

        int k;

        std::cin >> k;
        std::cout << prime[k] << '\n';

    }

    return 0;
}

记录 欧筛：

#include <iostream>
#include <cstring>
#include <bitset>

const int N = 1e8 + 5;

int prime[N];
std::bitset <N> isPrime;

int main(){

    std::cin.tie(0)->sync_with_stdio(0);

    int n,q,cnt = 0;

    std::cin >> n >> q;
    isPrime.set();
    isPrime[0] = isPrime[1] = false;
    for (int i = 2;i <= n;i++){

        if (isPrime[i]) prime[++cnt] = i;
        for (int j = 1;j <= cnt && i * prime[j] <= n;j++){

            isPrime[i * prime[j]] = false;
            if (i % prime[j] == 0) break;

        }

    }
    while (q--){

        int k;

        std::cin >> k;
        std::cout << prime[k] << '\n';

    }

    return 0;
}

记录