C Chương trình in hiệu quả tất cả các thừa số nguyên tố của một số đã cho?

Trong phần này, chúng ta sẽ xem cách chúng ta có thể lấy tất cả các thừa số nguyên 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 tất cả các thừa số nguyên tố của số này. Các thừa số nguyên tố của 1092 là 2, 2, 3, 7, 13. Để 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ì in ra 2 và chia số đó nhiều lần cho 2.

• 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 số, nếu số đó chia hết cho giá trị hiện tại, thì in ra và thay số bằng cách chia nó với số hiện tại rồi tiếp tục.

Hãy để chúng tôi xem thuật toán để hiểu rõ hơn.

Thuật toán

printPrimeFactors (n)

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

Ví dụ

#include<stdio.h>
#include<math.h>
void primeFactors(int n) {
   int i;
   while(n % 2 == 0) {
      printf("%d, ", 2);
      n = n/2; //reduce n by dividing this by 2
   }
   for(i = 3; i <= sqrt(n); i=i+2){ //i will increase by 2, to get only odd numbers
      while(n % i == 0) {
         printf("%d, ", i);
         n = n/i;
      }
   }
   if(n > 2) {
      printf("%d, ", n);
   }
}
main() {
   int n;
   printf("Enter a number: ");
   scanf("%d", &n);
   primeFactors(n);
}

Đầu ra

Enter a number: 24024
2, 2, 2, 3, 7, 11, 13,