Tìm tổng các ước số chẵn của một số trong C++

Chương trình tìm tất cả ước số chẵn của một số và tính tổng chúng.

Ví dụ

Input: 30
Ước chẵn: 2 + 6 + 10 + 30 = 48
Output: 48

Phương pháp 1: Duyệt tất cả ước số

Tìm tất cả ước, lọc ra số chẵn, cộng dồn.

Phương pháp 2: Công thức toán học (hiệu quả hơn)

Tổng ước số = (1 + p₁¹ + p₁² + ... + p₁^a₁) × (1 + p₂¹ + ... + p₂^a₂) × ... × (1 + pₖ¹ + ... + pₖ^aₖ)

Trong đó pᵢ là thừa số nguyên tố, aᵢ là số mũ.

Chỉ cần ước chẵn → nếu số lẻ thì không có ước chẵn → trả về 0. Nếu số chẵn, tách thừa số 2 ra riêng.

Code ví dụ (Phương pháp 2)

#include <iostream>
#include <cmath>
using namespace std;

int sumEvenFactors(int n) {
    int original = n;
    
    // Nếu số lẻ -> không có ước chẵn
    if (n % 2 != 0)
        return 0;
    
    int result = 1;
    
    // Xử lý thừa số 2 riêng
    int count = 0;
    while (n % 2 == 0) {
        count++;
        n /= 2;
    }
    // Tổng các lũy thừa của 2: 2^1 + 2^2 + ... + 2^count
    // = 2 * (2^count - 1) / (2 - 1) = 2^(count+1) - 2
    int sum2 = (1 << (count + 1)) - 2; // 2^(count+1) - 2
    result *= sum2;
    
    // Xử lý các thừa số lẻ
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) {
            count = 0;
            int curr_term = 1;
            int curr_sum = 1;
            while (n % i == 0) {
                count++;
                n /= i;
                curr_term *= i;
                curr_sum += curr_term;
            }
            result *= curr_sum;
        }
    }
    
    // Nếu n còn lại là số nguyên tố > 2
    if (n > 2)
        result *= (1 + n);
    
    return result;
}

int main() {
    int n = 12;
    cout << "Tong cac uoc so chan cua " << n << " la " << sumEvenFactors(n);
    return 0;
}

Kết quả

Tong cac uoc so chan cua 12 la 24

Giải thích: Ước của 12: 1, 2, 3, 4, 6, 12. Ước chẵn: 2, 4, 6, 12. Tổng = 24.

Độ phức tạp

• Phương pháp 1: O(n)
• Phương pháp 2: O(√n) - nhanh hơn đáng kể cho số lớn