Chương trình C/C++ tìm tích các ước nguyên tố duy nhất của một số

Trong phần này chúng ta sẽ xem cách lấy tích của các ước nguyên tố duy nhất của một số một cách hiệu quả. Có một số n = 1092, chúng ta phải lấy tích các ước nguyên tố duy nhất của nó. Các ước nguyên tố của 1092 là 2, 2, 3, 7, 13. Vậy các ước nguyên tố duy nhất là {2, 3, 7, 13}, tích là 546. Để giải quyết bài toán này, chúng ta phải tuân theo quy tắc sau:

• Khi số chia hết cho 2, nhân 2 vào tích, và chia số cho 2 liên tục, thì các 2 tiếp theo sẽ bị bỏ qua.
• Bây giờ số phải là lẻ. Bắt đầu từ 3 đến căn bậc hai của số, nếu số chia hết cho giá trị hiện tại, nhân ước vào tích, và thay đổi số bằng cách chia nó cho số hiện tại rồi tiếp tục. Các ước tiếp theo bị bỏ qua như trên.
• Và cuối cùng nếu số lớn hơn 2, thì nó không phải 1, nên nhân số dư còn lại.

Hãy xem thuật toán để hiểu rõ hơn.

Thuật toán

uniquePrimeProduct(n)

begin
  prod := 1
  if n is divisible by 2, then
    prod := prod * 2
    n := n / 2
  end if
  while n is divisible by 2, do
    n := n / 2
  done
  for i := 3 to √n, increase i by 2, do
    if n is divisible by i, then
      prod := prod * i
      n := n / i
    end if
    while n is divisible by i, do
      n := n / i
    done
  done
  if n > 2, then
    prod := prod * n
  end if
end

Ví dụ

#include<stdio.h>
#include<math.h>

int uniquePrimeProduct(int n){
  int i, prod = 1;
  if(n % 2 == 0){
    prod *= 2;
    n = n/2;
  }
  while(n % 2 == 0){//skip next 2s
    n = n/2;
  }
  for(i = 3; i <= sqrt(n); i=i+2){ //i will increase by 2, to get only odd numbers
    if(n % i == 0){
      prod *= i;
      n = n/i;
    }
    while(n % i == 0){ //skip next i's
      n = n/i;
    }
  }
  if(n < 2){
    prod *= n;
  }
  return prod;
}

main() {
  int n;
  printf("Enter a number: ");
  scanf("%d", &n);
  printf("Product of prime factors: %d", uniquePrimeProduct(n));
}

Kết quả

Enter a number: 1092
Product of prime factors: 546