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

Ước Số Nguyên Tố Lớn Nhất

Tìm số nguyên tố lớn nhất chia hết cho một số nguyên dương.

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

  • Chia bỏ các thừa số từ nhỏ đến lớn
  • Dừng tại căn bậc hai của phần còn lại
  • Xử lý số lớn hiệu quả

Đề bài

Xem bản gốc (English)

Một số nguyên tố là số nguyên lớn hơn 1 và chỉ chia hết cho 1 và chính nó. Hãy tìm ước số nguyên tố lớn nhất của n. Nếu n là số nguyên tố, trả về n.

Cài đặt hàm largest_prime_factor(n).

Đầu vào

n: Số nguyên cần phân tích thừa số.

Đầu ra

Trả về ước số nguyên tố lớn nhất của n.

Ràng buộc

2 ≤ n ≤ 10¹². Không xét đầu vào 1 vì 1 không có ước số nguyên tố.

Ví dụ

Ví dụ 1
Đầu vào:
n = 84

Kết quả mong đợi:
expected = 7
Đầu vào:
long long n = 84;

Kết quả mong đợi:
long long expected = 7;
Đầu vào:
long n = 84;

Kết quả mong đợi:
long expected = 7;

Giải thích

84 = 2 × 2 × 3 × 7, nên ước số nguyên tố lớn nhất là 7.

Ví dụ 2
Đầu vào:
n = 13

Kết quả mong đợi:
expected = 13
Đầu vào:
long long n = 13;

Kết quả mong đợi:
long long expected = 13;
Đầu vào:
long n = 13;

Kết quả mong đợi:
long expected = 13;

Giải thích

13 là số nguyên tố nên chính nó là ước số nguyên tố lớn nhất.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Loại bỏ các ước nguyên tố nhỏ trước; giá trị còn lại chỉ có thể giảm, và thừa số cuối cùng chính là đáp án.

Gợi ý 2

Chỉ thử các ước đến căn bậc hai của phần dư hiện tại, và chia lặp lại khi chia hết.

Gợi ý 3

Nếu sau khi xét các ước nhỏ mà phần dư vẫn > 1, thì phần dư đó là số nguyên tố và cũng là thừa số lớn nhất.

Độ phức tạp mong đợi

thời gian O(√n), bộ nhớ phụ O(1)

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.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 949 ms - 4/5 Xem code
2 KKKaneki Ken Python 1,000 ms - 3/5 Xem code

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

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

Cảnh báo: Có 2 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.