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

Trong phần này, chúng ta sẽ xem cách lấy tổng của tất cả các ước số nguyên tố lẻ 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 của nó. Các ước nguyên tố của 1092 là 2, 2, 3, 7, 13. Tổng của tất cả các ước lẻ là 3+7+13 = 23. Để 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, bỏ qua ước đó 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ì cộng ước vào tổng, và thay đổi số bằng cách chia nó cho số hiện tại rồi tiếp tục.
• Cuối cùng, số dư cũng sẽ được cộng nếu số dư là lẻ.

Hãy xem thuật toán để hiểu rõ hơn.

Thuật toán

printPrimeFactors(n)

begin
  sum := 0
  while n is divisible by 2, do
    n := n / 2
  done
  for i := 3 to √n, increase i by 2, do
    while n is divisible by i, do
      sum := sum + i
      n := n / i
    done
  done
  if n > 2, then
    if n is odd, then
      sum := sum + n
    end if
  end if
end

Ví dụ

#include<stdio.h>
#include<math.h>

int sumOddFactors(int n) {
  int i, sum = 0;
  while(n % 2 == 0) {
    n = n/2; //reduce n by dividing this by 2
  }
  //as the number is not divisible by 2 anymore, all factors are odd
  for(i = 3; i <= sqrt(n); i=i+2){ //i will increase by 2, to get only odd numbers
    while(n % i == 0) {
      sum += i;
      n = n/i;
    }
  }
  if(n > 2) {
    if(n%2 == 1)
      sum += n;
  }
  return sum;
}

main() {
  int n;
  printf("Enter a number: ");
  scanf("%d", &n);
  printf("Sum of all odd prime factors: %d", sumOddFactors(n));
}

Kết quả

Enter a number: 1092
Sum of all odd prime factors: 23