Chương trình C tìm ước nguyên tố lớn nhất của một số

Trong phần này, chúng ta sẽ xem cách lấy ước nguyên tố lớn 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 ước nguyên tố lớn nhất của nó. Các ước nguyên tố của 1092 là 2, 2, 3, 7, 13. Vậy lớn nhất là 13. Để giải quyết vấn đề này, chúng ta phải tuân theo quy tắc sau:

• Khi số chia hết cho 2, lưu 2 là lớn nhất, và chia số cho 2 liên tục.
• 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, lưu ước là lớn nhất, và thay đổi số bằng cách chia nó cho 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 1, nên lấy ước nguyên tố lớn nhất.

Hãy 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 √n, 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));
}

Kết quả

Enter a number: 24024
Max prime factor: 13