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ố 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 ước số của nó. Các ước số 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 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, bỏ qua ước số đó, và chia số cho 2 liên tục.
- Bây giờ số chắc chắn 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 số vào tổng, và thay đổi số bằng cách chia nó cho giá trị 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 chia hết cho 2, do n := n / 2 done for i := 3 đến √n, tăng i lên 2, do while n chia hết cho i, do sum := sum + i n := n / i done done if n > 2, then if n là lẻ, then sum := sum + n end if end if end
Ví dụ
#include<iostream> #include<cmath> using namespace std; int sumOddFactors(int n){ int i, sum = 0; while(n % 2 == 0){ n = n/2; //giảm n bằng cách chia cho 2 } //vì số không còn chia hết cho 2, tất cả ước số đều lẻ for(i = 3; i <= sqrt(n); i=i+2){ //i tăng 2 để chỉ lấy số lẻ while(n % i == 0){ sum += i; n = n/i; } } if(n > 2){ if(n%2 == 1) sum += n; } return sum; } main() { int n; cout << "Enter a number: "; cin >> n; cout <<"Sum of all odd prime factors: "<< sumOddFactors(n); }
Kết quả
Enter a number: 1092 Sum of all odd prime factors: 23