Hướng dẫn cho Phân tích thừa số nguyên tố


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame


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

  • \(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\)\(f''_i \in N\)

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

Nên số cách chọn phần tử \(d\)\((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

C++
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;
}


Bình luận


  • 0
    anhquan24    1:12 p.m. 13 Tháng 8, 2023

    bài này mình làm sàn nguyen tố cũng ac mà