Chương trình Python tính tích các thừa số nguyên tố duy nhất của một số

Trong bài viết này, chúng ta sẽ tìm hiểu về giải pháp cho bài toán dưới đây:

Đề bài − Cho một số n, chúng ta cần tìm tích của tất cả thừa số nguyên tố duy nhất của nó và trả về kết quả.

Ví dụ,

Input: num = 11
Output: Tích là 11
Giải thích: Ở đây, số đầu vào là 11 chỉ có 1 thừa số nguyên tố là 11. Và do đó tích của chúng là 11.

Cách tiếp cận 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 không & sau đó kiểm tra xem i có phải là số nguyên tố hay không, nếu có thì lưu tích vào biến product và tiếp tục quá trình này 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ả

6

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

Cách tiếp cận 2

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

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

• Nếu n là số nguyên tố và lớn hơn 2, thì n sẽ không 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
    # Thừa số nguyên tố 2
    if (n % 2 == 0):
        product *= 2
        while (n % 2 == 0):
            n = n / 2
    # n phải là số lẻ
    for i in range(3, int(math.sqrt(n)), 2):
        # Trong 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 bên dưới:

Kết luận

Trong bài viết này, chúng ta đã tìm hiểu về tích các thừa 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ả.