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

Đề bài

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).

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

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

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

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;

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;

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

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)

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.