Tích các ước số nguyên tố duy nhất của một số trong Python

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ố n, chúng ta cần tìm tích của tất cả các ước số nguyên tố duy nhất của nó và trả về kết quả.

Ví dụ

Input: num = 11
Output: Product is 11

Giải thích

Ở đây, số đầu vào là 11 chỉ có 1 ước số nguyên tố là 11. Và do đó tích của chúng là 11.

Cách 1

Sử dụng vòng lặp for từ i = 2 đến n+1 kiểm tra xem i có phải là ước của n và sau đó kiểm tra xem i có phải là số nguyên tố, nếu có thì lưu tích vào biến product và tiếp tục quá trình cho đến khi i = n.

Ví dụ

def productPrimeFactors(n):
    product = 1
    for i in range(2, n+1):
        if (n % i == 0):
            isPrime = 1
            for j in range(2, int(i/2 + 1)):
                if (i % j == 0):
                    isPrime = 0
                    break
            if (isPrime):
                product = product * i
    return product
# main
n = 18
print(productPrimeFactors(n))

Kết quả

120

Phạm vi của tất cả biến được hiển thị trong hình dưới đây:

Cách 2 (Hiệu quả hơn)

1) Khi n chia hết cho 2 (chẵn), in 2 và chia n cho 2.

2) Sau bước 1, n phải trở thành lẻ. Bây giờ bắt đầu vòng lặp for từ i = 3 đến căn bậc hai của n. Khi i chia hết n, in i và chia n cho i. Sau khi i không còn chia hết n, tăng i lên 2 và tiếp tục.

3) Nếu n là số nguyên tố và lớn hơn 2, thì n sẽ không trở thành 1 bằng hai bước trên. Do đó in n nếu nó lớn hơn 2.

Ví dụ

import math
def productPrimeFactors(n):
    product = 1
    # ước nguyên tố 2
    if (n % 2 == 0):
        product *= 2
        while (n % 2 == 0):
            n = n / 2
    # n phải là lẻ
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        # Khi i chia hết n, in i và chia n
        if (n % i == 0):
            product = product * i
            while (n % i == 0):
                n = n / i
    # n là số nguyên tố lớn hơn 2
    if (n > 2):
        product = product * n
    return product
# main()
n = 8
print(int(productPrimeFactors(n)))

Kết quả

2

Phạm vi của các biến được đề cập trong hình dưới đây:

Kết luận

Trong bài viết này, chúng ta đã học về tích các ước số nguyên tố duy nhất của một số cho trước với cách tiếp cận brute force và cách tiếp cận hiệu quả.