Chương trình Python tìm ước số nguyên tố lớn nhất của một số

Trong bài viết này, chúng ta sẽ học về giải pháp cho bài toán cho trước:

Đề bài

Cho một số nguyên dương n. Chúng ta cần tìm ước số nguyên tố lớn nhất của một số.

Phương pháp

• Phân tích thừa số của số cho trước bằng cách chia nó cho ước số của số.
• Giờ cập nhật liên tục ước số nguyên tố lớn nhất.

Ví dụ

import math
def maxPrimeFactor(n):
    # số phải chẵn
    while n % 2 == 0:
        max_Prime = 2
        n /= 2
    # số phải lẻ
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        while n % i == 0:
            max_Prime = i
            n = n / i
    # số nguyên tố lớn hơn 2
    if n > 2:
        max_Prime = n
    return int(max_Prime)
# Driver code to test above function
n = 15
print(maxPrimeFactor(n))

Time complexity: O(sqrt(n))

Auxiliary space: O(1)

Kết quả

5

Tất cả biến được khai báo trong khung toàn cục như hình dưới đây:

Kết luận

Trong bài viết này, chúng ta đã học về cách tìm ước số nguyên tố lớn nhất của một số.