Tất cả thử thách
Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Phân tích thừa số nguyên tố

Phân tích một số thành các thừa số nguyên tố, liệt kê từ nhỏ đến lớn, kể cả các thừa số lặp lại.

Bạn sẽ học được gì

  • Chia hết mỗi thừa số đúng bằng số lần nó xuất hiện
  • Dừng phép chia thử khi d × d vượt quá phần còn lại
  • Nhận ra phần dư lớn hơn 1 còn sót lại là một thừa số nguyên tố

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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].

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.