Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [An toàn thông tin] Phân tích thừa số nguyên tố

    Độ an toàn của hệ mật RSA dựa trên độ khó của bài toán phân tích một hợp số lớn thành tích các thừa số nguyên tố. Trong bài này, ta xét bài toán ở quy mô nhỏ, có thể giải bằng thuật toán chia thử (trial division).

    Cho số nguyên dương nnn. Hãy phân tích nnn thành tích các lũy thừa của các số nguyên tố phân biệt: n=p1e1×p2e2×⋯×pkekn = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k}n=p1e1​​×p2e2​​×⋯×pkek​​ với p1<p2<⋯<pkp_1 < p_2 < \cdots < p_kp1​<p2​<⋯<pk​.

    Ví dụ: với n=360n = 360n=360, ta có 360=23×32×51360 = 2^3 \times 3^2 \times 5^1360=23×32×51.

    • Định dạng đầu vào:

      Một dòng duy nhất chứa số nguyên nnn (2≤n≤10122 \le n \le 10^{12}2≤n≤1012).

    • Định dạng đầu ra:

      In ra một dòng theo định dạng p1^e1 * p2^e2 * ... * pk^ek, các thừa số nguyên tố sắp xếp tăng dần, phân tách bởi chuỗi * (dấu cách, dấu sao, dấu cách). Nếu nnn là số nguyên tố thì chỉ in n^1.

    Ví dụ:

    Đầu vào:

    2

    Đầu ra:

    2^1

    Đầu vào:

    4

    Đầu ra:

    2^2

    Đang tải editor...