Trong phần này, chúng ta sẽ thấy cách lấy tổng của tất cả các ước số nguyên tố chẵn của một số một cách hiệu quả. Có một số n = 480, chúng ta phải lấy tất cả các ước số của nó. Các ước số nguyên tố của 480 là 2, 2, 2, 2, 2, 3, 5. Tổng của tất cả các ước chẵn là 2+2+2+2+2 = 10. Để giải quyết bài toán này, chúng ta phải tuân theo quy tắc sau:
- Khi số chia hết cho 2, cộng chúng vào tổng, và chia số cho 2 liên tục.
- Bây giờ số chắc chắn là lẻ. Vì vậy chúng ta sẽ không tìm thấy ước số nào là chẵn. Sau đó chỉ cần bỏ qua các ước số đó.
Hãy xem thuật toán để hiểu rõ hơn.
Thuật toán
printPrimeFactors(n): begin sum := 0 while n chia hết cho 2, do sum := sum + 2 n := n / 2 done end
Ví dụ
#include<iostream> using namespace std; int sumEvenFactors(int n){ int i, sum = 0; while(n % 2 == 0){ sum += 2; n = n/2; //giảm n bằng cách chia cho 2 } return sum; } main() { int n; cout << "Enter a number: "; cin >> n; cout << "Sum of all even prime factors: "<< sumEvenFactors(n); }
Kết quả
Enter a number: 480 Sum of all even prime factors: 10