Kiểm tra số có đúng 4 ước số khác nhau trong C++

Cho Q truy vấn, mỗi truy vấn một số N. Xác định xem N có đúng 4 ước số dương khác nhau hay không.

Ví dụ

Q = 3, queries = {4, 6, 15}
4: ước {1,2,4} → 3 ước → NO
6: ước {1,2,3,6} → 4 ước → YES
15: ước {1,3,5,15} → 4 ước → YES

Điều kiện cần và đủ

Số N có đúng 4 ước số ⇔ N thỏa mãn một trong hai dạng:

1. N = p³ với p là số nguyên tố. Ước: 1, p, p², p³.
2. N = p₁ × p₂ với p₁, p₂ là hai số nguyên tố khác nhau. Ước: 1, p₁, p₂, p₁p₂.

Phương pháp 1: Kiểm tra từng truy vấn O(√N)

Đếm ước bằng cách duyệt đến √N. Phù hợp Q nhỏ, N ≤ 10⁹.

Phương pháp 2: Tiền xử lý Sieve O(N log log N) + O(1) mỗi truy vấn

Áp dụng khi N ≤ 10⁶ và Q lớn.

• Sieve tìm tất cả số nguyên tố ≤ N.
• Đánh dấu has4[N+1]: true nếu p³ ≤ N hoặc p₁·p₂ ≤ N.
• Trả lời truy vấn O(1).

Chương trình C++ (Phương pháp 2)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000000;
bool hasFourFactors[MAXN + 1];

void precompute() {
    vector isPrime(MAXN + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= MAXN; i++)
        if (isPrime[i])
            for (int j = i * i; j <= MAXN; j += i)
                isPrime[j] = false;
    
    vector primes;
    for (int i = 2; i <= MAXN; i++)
        if (isPrime[i]) primes.push_back(i);
    
    // Dạng p^3
    for (int p : primes) {
        long long p3 = 1LL * p * p * p;
        if (p3 > MAXN) break;
        hasFourFactors[p3] = true;
    }
    // Dạng p1 * p2
    for (size_t i = 0; i < primes.size(); i++) {
        for (size_t j = i + 1; j < primes.size(); j++) {
            long long prod = 1LL * primes[i] * primes[j];
            if (prod > MAXN) break;
            hasFourFactors[prod] = true;
        }
    }
}

int main() {
    precompute();
    int Q = 3;
    int query[] = {3, 6, 15};
    for (int i = 0; i < Q; i++) {
        cout << "So " << query[i] << (hasFourFactors[query[i]] ? " co " : " KHONG co ")
             << "dung 4 uoc so.\n";
    }
    return 0;
}

Kết quả

So 3 KHONG co dung 4 uoc so.
So 6 co dung 4 uoc so.
So 15 co dung 4 uoc so.