Spoiler Alert

Hint 1

• Chia dần các ước nguyên tố của \(n\) đồng thời tăng biến đếm

Đưa các ước nguyên tố \(p\) và số lần bị chia vào một mảng
Xuất các số nguyên tố theo tần số

Hint 2

• Khi \((p\ |\ n)\) thì \(p * \frac{n}{p} = n\)

\(\Leftrightarrow p\) là ước của \(n\) thì \(\frac{n}{p}\) cũng là ước của \(n\)

Ta có thể chạy tới \(\sqrt{n}\) để đếm số ước

• Thay vì thử từng số nguyên tố, ta có thể từng số \(i\) tăng dần từ 2 và kiểm tra tính chia hết

Nếu \(n\) không chia hết \(i\) thì bỏ qua (vì nó không phải ước nguyên tố)

Ngược lại ta sẽ thêm số nguyên tố \(i\) vào mảng và chia \(n\) dần đồng thời tăng số lần chia

Hint 3

• Có \(n = p_1 ^ {f_1} \times p_2 ^ {f_2} \times ... \times p_k ^ {f_k}\) với \(f_i \in N\)

Thì \(d = p_1 ^ {f''_1} \times p_2 ^ {f''_2} \times ... \times p_k ^ {f''_k}\) là ước của \(n\) \(\forall f''_i ≤ f_i\) và \(f''_i \in N\)

Mỗi ước nguyên tố \(pi\) có \(f''_i\) cách chọn

Nên số cách chọn phần tử \(d\) là \((f''_1 + 1) \times (f''_2 + 1) \times ... \times (f''k + 1)\)

Vậy khi phân tích số nguyên tố từ \(n\) ta dễ dàng tìm số ước trong \(O(log (log n))\)

• Nhận xét rằng nếu với mọi số nguyên \(2 ≤ x ≤ √n\) không phải là ước của \(n\) thì \(n\) là số nguyên tố

Chạy tới √n hoặc tới khi \(n = 1\) để phân tích thừa số nguyên tố

Nếu sau đó \(n > 1\) thì \(n\) là số nguyên tố

Reference AC code | \(O(\sqrt n)\) time | \(O(\frac{\log n}{\log(\log n)})\) auxiliary space | Factorization

int main()
{
    //// Input
    int n = readInt();
    int sqrtn = sqrt(n);

    pair<int, int> divs; /// Divisors vector<p, f> = <prime divisor, frequency>

    /// p = 2 case
    if (n % 2 == 0)
    {
        divs.push_back(make_pair(2, 0)); /// Add new prime p = (2)
        do divs.back().se++, n /= 2; while (n % 2 == 0);
    }

    /// prime > 2 is odd, we dont have to care about even numbers
    for (int i = 3; i <= sqrtn; i += 2)
    {
        if (n % i != 0) continue;
        divs.push_back(make_pair(i, 0)); /// Add new prime p = (i)
        do divs.back().se++, n /= i; while (n % i == 0);
        if (n == 1) break; /// we can divide more
    }

    /// n is prime
    if (n > 1) divs.push_back(make_pair(n, 1));

    /// Output
    int p = divs.size();
    int count = 1;
    for (int i = 0; i + 1 < p; ++i)
    {
        count *= (divs[i].second + 1);
        while (divs[i].second-->0) cout << divs[i].first << '*';
    }
    count *= (divs.back().second + 1);
    while (divs.back().second-->1) cout << divs.back().first << '*';
    cout << divs.back().first << endl;

    cout << count; /// Number of divisors
    return 0;
}