Đề bài
Mọi số nguyên lớn hơn 1 đều viết được thành tích các số nguyên tố theo đúng một cách duy nhất, nếu không tính thứ tự các thừa số (định lý cơ bản của số học). Ví dụ, 360 = 2 × 2 × 2 × 3 × 3 × 5. Việc tìm ra danh sách đó gọi là phân tích thừa số nguyên tố.
Hãy viết prime_factorization(n).
n có thể lớn tới 10^12, nên cách làm kinh điển là phép chia thử: chia cho 2 chừng nào còn chia hết, rồi đến 3, và cứ thế tiếp tục. Bạn chỉ cần thử các ước d khi d × d ≤ phần còn lại của n; phần nào lớn hơn 1 còn sót lại ở cuối thì chính nó là số nguyên tố. Nhờ vậy khối lượng công việc chỉ khoảng √n ≈ 10^6 bước, kể cả khi n là một số nguyên tố lớn hoặc là tích của hai số nguyên tố lớn.
Đầu vào
n: Số cần phân tích.
Đầu ra
Trả về các thừa số nguyên tố của n theo thứ tự tăng dần, mỗi số nguyên tố lặp lại đúng bằng số lần nó chia hết n, sao cho tích của cả danh sách bằng n. Với n = 1, trả về danh sách rỗng. Nếu n là số nguyên tố, danh sách chỉ có một phần tử là n.
Ràng buộc
1 ≤ n ≤ 10^12
Ví dụ
Đầu vào:
n = 360
Kết quả mong đợi:
expected = [2, 2, 2, 3, 3, 5]
Đầu vào:
long long n = 360;
Kết quả mong đợi:
std::vector<long long> expected = {2, 2, 2, 3, 3, 5};
Đầu vào:
long n = 360;
Kết quả mong đợi:
long[] expected = new long[] {2, 2, 2, 3, 3, 5};
Giải thích
360 = 2 × 180 = 2 × 2 × 90 = 2 × 2 × 2 × 45 = 2 × 2 × 2 × 3 × 15 = 2 × 2 × 2 × 3 × 3 × 5, nên kết quả là [2, 2, 2, 3, 3, 5].
Đầu vào:
n = 97
Kết quả mong đợi:
expected = [97]
Đầu vào:
long long n = 97;
Kết quả mong đợi:
std::vector<long long> expected = {97};
Đầu vào:
long n = 97;
Kết quả mong đợi:
long[] expected = new long[] {97};
Giải thích
Không số nguyên tố nào đến √97 ≈ 9.8 (2, 3, 5, 7) chia hết 97, nên 97 là số nguyên tố và kết quả là [97].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Chia cho 2 chừng nào còn chia hết, rồi chuyển sang 3, 5, 7, ...
Gợi ý 2
Mỗi khi tìm được một thừa số thì thu nhỏ n lại, và so sánh d × d với giá trị n đã thu nhỏ.
Gợi ý 3
Nếu sau vòng lặp còn lại một số lớn hơn 1 thì đó là thừa số nguyên tố lớn nhất.
Độ phức tạp mong đợi
thời gian O(√n), bộ nhớ phụ O(log n) cho kết quả
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.