Bài 7. Số ước nguyên tố
Tên file: uocnto.py hoặc uocnto.cpp
Hãy đếm trong đoạn [a, b] các số nguyên dương thỏa mãn yêu cầu: số lượng các ước của nó là một số nguyên tố.
Input: uocnto.inp
• Dòng 1: chứa số T là số lượng các đoạn cần đếm
• Dòng 2: T dòng tiếp theo, mỗi dòng chứa một cặp số nguyên a và b
Output: uocnto.out
• Gồm T dòng, mỗi dòng là kết quả tương ứng với input
Ví dụ:
Uocnto.inp
2
25
1 100
Uocnto.out
4
32
Ràng buộc
•
Subtask1: có 30% số điểm 1 ≤ a ≤ b ≤ 200 và T ≤ 100
Subtask2: có 30% số điểm 1 ≤ a ≤ b ≤ 2000 và T ≤ 1000
Subtask3: có 40% còn lại 1 ≤ a ≤ b ≤ 106 và T ≤ 105
•
•

#include <bits/stdc++.h>
#define N int(1e6+1)
using namespace std;
int nt[N], c[N];
void sangnt()
{
    fill(nt+1,nt+N+1,1);
    fill(c+1,c+N+1,1);
    nt[1] = c[1] = 0;
    for (int i=2; i*i<=N; i++)
    if (nt[i]==1)
        for (int j=i*i; j<=N; j+=i)
            nt[j] = c[j] = 0;
}
int demuoc(int x)
{
    int souoc = 1, i = 2;
    while (i*i <= x)
    {
        int d = 0;
        while (x % i == 0)
        {
            d++;
            x = x/i;
        }
        souoc *= 2*d + 1;
        i++;
    }
    if (x > 1) souoc *= 3;
    return souoc;
}
void init()
{
    sangnt();
    for (int i=2; i*i<=N; i++)
    {
        int k = demuoc(i);
        if (nt[k])
            c[i*i] = 1;
    }
    for (int i=1; i<=N; i++)
        c[i] += c[i-1];
}
int main()
{
    freopen("uocnto.inp","r",stdin);
    freopen("uocnto.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    init();
    int t;
    cin >> t;
    while (t--)
    {
        int a, b;
        cin >> a >> b;
        cout << c[b] - c[a-1] << '\n';
    }
    return 0;
}