Chương trình C in hiệu quả tất cả ước nguyên tố của một số cho trước

Trong phần này, chúng ta sẽ xem cách lấy tất cả các ước nguyên 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ất cả ước nguyên tố của nó. Các ước nguyên tố của 1092 là 2, 2, 3, 7, 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, in 2 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, thì in, và thay đổi số bằng cách chia nó cho số hiện tại rồi tiếp tục.

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

Kết quả

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