steve of atkin 速度 $O(n/loglogn)$

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<int> atkin_sieve(int limit) {
    if (limit < 2) return {};

    vector<bool> is_prime(limit + 1, false);
    vector<int> primes;

    // Preliminary sieve for primes up to the square root of the limit
    int sqrt_limit = sqrt(limit);
    vector<bool> preliminary(limit + 1, false);

    for (int x = 1; x <= sqrt_limit; x++) {
        for (int y = 1; y <= sqrt_limit; y++) {
            int n = (4 * x * x) + (y * y);
            if (n <= limit && (n % 12 == 1 || n % 12 == 5))
                preliminary[n] = !preliminary[n];

            n = (3 * x * x) + (y * y);
            if (n <= limit && n % 12 == 7)
                preliminary[n] = !preliminary[n];

            n = (3 * x * x) - (y * y);
            if (x > y && n <= limit && n % 12 == 11)
                preliminary[n] = !preliminary[n];
        }
    }

    // Mark all multiples of squares as non-prime
    for (int n = 5; n <= sqrt_limit; n++) {
        if (preliminary[n]) {
            int x = n * n;
            for (int k = x; k <= limit; k += x) {
                preliminary[k] = false;
            }
        }
    }

    // Add remaining primes to the primes vector
    primes.push_back(2);
    primes.push_back(3);
    for (int n = 5; n <= limit; n++) {
        if (preliminary[n]) {
            primes.push_back(n);
        }
    }

    return primes;
}

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> primes = atkin_sieve(n);
    while (q--) {
        int k;
        cin >> k;
        cout << primes[k - 1] << endl;
    }
    return 0;
}