โปรแกรม Java หาผลรวมตัวหารที่เป็นเลขคู่ของจำนวน

โจทย์: Sum of Even Factors

ตัวอย่าง: 36 → factors: 1,2,3,4,6,9,12,18,36 → even factors: 2,4,6,12,18,36 → sum = 78

สูตรคณิตศาสตร์ (Prime Factorization)

ถ้า n = 2^k × p1^e1 × p2^e2 × ... (k ≥ 1 เพื่อให้มี even factors)

Sum of even factors = (2^1 + 2^2 + ... + 2^k) × Π(1 + p + p² + ... + p^e)

= 2(2^k - 1) × Π(p^(e+1) - 1)/(p - 1) สำหรับ odd primes p

ตัวอย่างโค้ด (ใช้สูตร)

public class Demo {
    public static int sumEvenFactors(int n) {
        if (n % 2 != 0) return 0; // เลขคี่ ไม่มี even factors
        
        int result = 1;
        
        // Handle factor 2
        int count2 = 0;
        while (n % 2 == 0) {
            n /= 2;
            count2++;
        }
        // Sum of powers of 2: 2 + 4 + ... + 2^k = 2(2^k - 1)
        int sum2 = 2 * ((1 << count2) - 1);
        result *= sum2;
        
        // Handle odd prime factors
        for (int p = 3; p * p <= n; p += 2) {
            if (n % p == 0) {
                int sumP = 1;
                int term = 1;
                while (n % p == 0) {
                    n /= p;
                    term *= p;
                    sumP += term;
                }
                result *= sumP;
            }
        }
        
        // Remaining prime > sqrt(n)
        if (n > 1) {
            result *= (1 + n);
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        int n = 36;
        System.out.println("Sum of even factors of " + n + " = " + sumEvenFactors(n));
    }
}

ผลลัพธ์

Sum of even factors of 36 = 78

วิธี Brute Force (เข้าใจง่าย, ช้ากว่า)

static int sumEvenFactorsBrute(int n) {
    int sum = 0;
    for (int i = 2; i <= n; i += 2) {
        if (n % i == 0) sum += i;
    }
    return sum;
}

Time: O(n) vs Formula: O(√n)