Spoiler Alert

Approach

• Xét bài toán con, với mỗi số thì tổng số mũ là bao nhiêu

Gọi kết quả thu được với mỗi phần tử \(A_i\) nhận vào là \(res_i\)

Tổng giá trị cả mảng là \(\sum_{i=1}^n{res_i}\)

Ta cần tìm giá trị nhỏ nhất, nên ta sẽ loại đi kết quả lớn nhất là \(\max\left(res_i\right)\)

Vậy kết quả cần tìm là \(\sum_{i=1}^n{res_i} - \max\left(res_i\right)\)

Hint 1

• Duyệt \(\forall p\) nguyên tố \(\leq n\)

Chia dần \(n\) cho \(p\) và tăng biến đếm

Khi \(n = 1\) thì ngừng và xuất kết quả

Hint 2

• Với \(1 \leq a \leq b \leq n\) \(^{(1)}\) ta có \(n = a \times b\) \(^{(2)}\)

\((2) \Leftrightarrow \sqrt n \times \sqrt n = a \times b\) mà từ \((1) \Leftrightarrow 1 \leq a \leq \sqrt n\leq b \leq n\)

Từ đây rút ra nhận xét về cận trên của số nguyên tố \(p\) trong trương hợp \(n\) không phải số nguyên tố

Hint 3

• Ta có thể không cần kiểm tra tính nguyên tố của số \(p\)

Thay vào đó ta duyệt từng ước \(d\) nhỏ nhất khác 1 của \(n\) và chia dần \(n\) cho \(d\) tới khi không chia được nữa thì duyệt tới ước lớn tiếp theo của \(n\) hiện tại

Khi đó, ta chắc chắn rằng \(d\) là số nguyên tố, và khi chia \(n\) dần thì sẽ loại khỏi \(n\) các thừa số nguyên tố \(d\) đó đi. Nên ước nhỏ nhất tiếp theo của \(n\) cũng là số nguyên tố.

Hint 4

• Ta chỉ cần duyệt các số nguyên tố \(p\) bé hơn \(\sqrt n\)

Từ nhận xét trên: Hợp số \(n\) có ước nguyên tố \(p \leq \sqrt n\)

Ta có thể kiểm tra xem \(n\) có phải số nguyên tố hay không trong \(O(\sqrt n)\) và cũng có thể loại các ước nguyên tố \(p\) trong \(O(\sqrt n)\)

Hint 5

• Ta có thể không cần kiểm tra \(n\) có nguyên tố hay không

Khi ta loại các ước \(p \leq \sqrt n\) nguyên tố ra khỏi \(n\) thì nếu sau quá trình đó, \(n > 1\) thì \(n\) là số nguyên tố

Chứng minh: Vì ta loại hết các ước nguyên tố \(p \leq n\). Nên khi \(n > 1\) thì \(p = n\) chưa bị loại

Reference AC code | \(O(n \sqrt{max\_val})\) time | \(O(\sqrt{max\_val})\) query | \(O(1)\) auxiliary space | Factorization

int query(int n)
{
    int res = 0;
    int sqrtn = sqrt(n);
    for (int p = 2; (p <= n) && (p <= sqrtn); ++p) /// p <= n (hien tai) va p <= sqrtn (truoc do) thi duyet tiep
    {
        while (n % p == 0) /// Trong khi n chia het cho p
        {
            n /= p;
            res++;
        }
    }
    if (n > 1) res++; /// n la so nguyen to

    return res;
}

Another Approach

• Ta cũng có thể tìm ước nguyên tố nhỏ nhất của mọi số \(x \leq n\) trong \(O(n)\)

Cải tiến sàng nguyên tố Eratosthenes

\(lpf[x] =\) min divisor prime \(p\) of \(x\)

Reference AC code | \(O(n \log_2{max\_val})\) time | \(O(\log_2{max\_val})\) query | \(O(n)\) auxiliary space | Online Solving, Sieve, Factorization

vector<int> prime;
vector<int> lpf; /// Lowest prime factor
void sieve(int lim = LIM)
{
    prime.assign(1, 2);
    lpf.assign(lim + 1, 2);

    for (int i = 3; i <= lim; i += 2) {
        if (lpf[i] == 2) prime.pb(lpf[i] = i);
        for (int j = 0; j < sz(prime) && prime[j] <= lpf[i] && prime[j] * i <= lim; ++j)
            lpf[prime[j] * i] = prime[j];
    }
}

int query(int n)
{
    int res = 0;
    while ((n > 1) && (n % lpf[n] == 0)) res++, n /= lpf[n];
    return res;
}

int main()
{
    ll sum = 0;
    int mx = 0;
    for (int n = readInt(); n--; )
    {
        int cnt = solve(readInt());
        mx = max(mx, cnt);
        sum += cnt;
    }

    cout << sum - mx;
    return 0;
}