Thuật toán trâu

Với mỗi số ~n~ từ ~a~ đến ~b~, ta xét tất cả các ước của ~n~ rồi kiểm tra số đó có phải nguyên tố hay không.

Thuật toán tối ưu hơn:

Một số ~n~ có ~k~ ước nguyên tố khác nhau đồng nghĩa với trong cách phân tích thừa số nguyên tố của ~n~, có đủ ~k~ thừa số nguyên tố. Ví dụ ~20~ có ~2~ ước thừa số nguyên tố khác nhau ~(20 = 2 \times 2 \times 5, 2~ ước nguyên tố là ~2~ và ~5)~.

Đến đây thì ta sử dụng sàng nguyên tố để phân tích thừa số nguyên tố, sử dụng kĩ thuật Prefix Sum để trả lời mỗi truy vấn trong ~O(1)~ với đoạn ~[L,R]~

Code mẫu

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <math.h>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <assert.h>

#define BIT(x,pos) (((x)>>(pos)) & 1LL)
#define _(x) (1LL<<(x))
#define bitCnt(x) __builtin_popcountll(x)
#define turnOn(x,pos) ((x) = (_(pos)))
#define turnOff(x,pos) ((x) &= ~(_(pos)))
#define flipBit(x,pos) ((x) ^= (_(pos)))
#define lowBit(x) ((x) & (-x))
#define turnAll(x) (_(x)-1LL)

#define name "test"
#define nameTask ""
#define fastIO ios::sync_with_stdio(false); cin.tie(0);

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

const int N = 1E6;

int f[8][N+9];
int cnt[N+9];
bool ck[N+9];

void sieve()
{
    for (int i = 2;i <= N; ++i)
        if (ck[i] == 0)
            for (int j = 2*i;j <= N; j += i)
            {
                ck[j] = 1;
                cnt[j]++;
            }

    ck[1] = ck[0] = 1;
    for (int i = 1;i <= N; ++i)
        if (ck[i] == 0) cnt[i] = 1;

    for (int k = 1;k <= 7; ++k)
        for (int j = 1;j <= N; ++j)
            f[k][j] = f[k][j-1] + (cnt[j] == k);
}

int main()
{
    fastIO


    sieve();

    int q;
    cin>>q;

    while (q--)
    {
        int l, r, k;
        cin>>l>>r>>k;

        cout<<f[k][r] - f[k][l-1]<<"\n";
    }
}