\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-force>}}\)

• Với từng số đếm thử trong khoảng \([2, 10^5]\) có bao nhiêu số thỏa mãn

\(\color{orange}{\text{Hint 2 <Sieving> <Precalculation>}}\)

• Nhận xét mọi số lớn hơn 10^5 đều không thể làm ước của các số trong khoảng \([2, 10^5]\) nên kết quả còn không

• Phần còn lại chúng ta có thể tiền xử lí dể trả lời truy vấn nhanh hơn

• Chúng ta có thể lấy tất cả các số nguyên tố bằng phép sàng

Sau đó với mỗi số nguyên tố từ nhỏ tới lớn ta gàn các bội chưa bị đánh dấu bằng giá trị nguyên tố đó

Duyệt qua các số bị đánh dấu và tăng số lần xuất hiện của số nguyên tố lên

\(\color{orange}{\text{Hint 3 <Optimization>}}\)

• Kết hợp cả việc sàng và việc đánh dấu vào một, ta có thể làm trong thời gian tuyến tính \(O(n)\)

• Chúng ta có thể đánh dấu vị trí của số nguyên tố để xuất kết quả trong \(O(1)\)

\(\color{green}{\text{Preference AC Code }}\): Precalculation, Sieving, Online Solving

\(^{^{\color{purple}{\text{Complexity : }} O(n)\ \color{purple}{\text{precalculation time}}\ || O(1)\ \color{purple}{\text{query time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

vector<int> prime, lpf, cnt, pos;
void sieve(int lim)
{
    prime.assign(1, 2);
    cnt.assign(1, lim / 2);
    lpf.assign(lim + 1, 2);
    pos.assign(lim + 1, 0);

    for (int i = 3; i <= lim; i += 2) {
        if (lpf[i] == 2)
        {
            prime.push_back(lpf[i] = i);
            pos[i] = prime.size();
            cnt.push_back(1);
        }

        for (int j = 0; j < int(prime.size()) && prime[j] <= lpf[i] && prime[j] * i <= lim; ++j)
        {
            lpf[prime[j] * i] = prime[j];
            cnt[j]++;   
        }
    }
}

int main()
{
    sieve(1e5);
    for (int q = readInt(); q--; )
    {
        ll p;
        getUnsign(p);
        if (p > 1e5)
        {
            cout << 0 << '\n';
            continue;
        }

        cout << cnt[pos[p]] << '\n';
    }


    return 0;
}

\(\color{purple}{\text{Question}}\)

• Bạn có thể giải nó với không gian \(O(\sqrt{n})\) hay không ?