C Chương trình tìm thừa số nguyên tố lớn 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 thừa số nguyên tố lớn 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 lấy thừa số nguyên tố lớn 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 lớn nhất là 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ì tích 2 là lớn nhất 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ì lưu thừa số là lớn nhất và thay đổi số bằng cách chia nó với số hiện tại rồi tiếp tục.

• 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 lấy thừa số nguyên tố tối đa.

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

Thuật toán

getMaxPrimeFactors (n)

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

Ví dụ

#include<stdio.h>
#include<math.h>
int getMaxPrimeFactor(int n) {
   int i, max = -1;
   while(n % 2 == 0) {
      max = 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) {
         max = i;
         n = n/i;
      }
   }
   if(n > 2) {
      max = n;
   }
   return max;
}
main() {
   int n;
   printf("Enter a number: ");
   scanf("%d", &n);
   printf("Max prime factor: %d", getMaxPrimeFactor(n));
}

Đầu ra

Enter a number: 24024
Max prime factor: 13