• Một cách đơn giản để tìm thừa số nguyên tố nhỏ nhất của các số từ ~2~ đến ~k~ là với mỗi số, ta tìm ước nhỏ nhất của nó.
• Nhận thấy rằng, trên đoạn ~[2, k]~ có khoảng ~\frac{k}{2}~ số chia hết cho ~2~, ~\frac{k}{3}~ số chia hết cho ~3~..., ~\frac{k}{x}~ số chia hết cho số nguyên tố ~x~ ~(x \le \sqrt{k})~, vậy độ phức tạp khi duyệt không quá ~k \times \log \sqrt{k}~

Subtask ~1~

• Với mỗi số trên đoạn ~[2, k]~, ta tìm trong ~a~ liệu có số đó và cộng vào bảng kết quả.
• Độ phức tạp: ~O(n \times k \times \log \sqrt{k})~.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1005;

int n, k, a[maxn], ans[maxn];

void phan_tich(int x)
{
    for(int i = 2; i*i <= x; i++)
        if (x%i == 0){
            for(int j = 1; j <= n; j++)
                if (a[j] == i){
                    ans[j]++;
                }
            return;
        }
    for(int i = 1; i <= n; i++)
        if (a[i] == x){
            ans[i]++;
        }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    freopen("zfactor.inp", "r", stdin);
    freopen("zfactor.out", "w", stdout);

    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 2; i <= k; i++) phan_tich(i);
    for(int i = 1; i <= n; i++) cout<<ans[i]<<'\n';

    return 0;
}

Subtask ~2~;

• Thay vì duyệt lại cả mảng ~a~ mỗi khi phân tích, ta đánh dấu vào bảng giá trị và chỉ cần duyệt mảng ~a~ ~1~ lần.
• Độ phức tạp: ~O(k \times \log \sqrt{k} + n)~.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 100005;

int n, k, a[maxn], cnt[maxn*10];

void phan_tich(int x)
{
    for(int i = 2; i*i <= x; i++)
        if (x%i == 0){
            cnt[i]++;
            return;
        }
    cnt[x]++;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    freopen("zfactor.inp", "r", stdin);
    freopen("zfactor.out", "w", stdout);

    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 2; i <= k; i++) phan_tich(i);
    for(int i = 1; i <= n; i++) cout<<cnt[a[i]]<<'\n';

    return 0;
}