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

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

• Khi số đó chia hết cho 2 thì nhân 2 với tích và chia số đó cho 2 liên tục thì 2s tiếp theo sẽ bị bỏ qua.

• Bây giờ con số phải là số lẻ. Bây giờ bắt đầu từ 3 đến căn bậc hai của một số, nếu số đó chia hết cho giá trị hiện tại, sau đó nhân thừa số thành tích, và đổi số bị chia với số hiện tại rồi tiếp tục. Tiếp theo là bỏ qua như trên

• Và cuối cùng nếu số lớn hơn 2, thì nó không phải là 1, vì vậy hãy nhân số còn lại.

Hãy cho chúng tôi xem thuật toán để có ý tưởng tốt 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 √𝑛, 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));
}

Đầu ra

Enter a number: 1092
Product of prime factors: 546