โปรแกรม Java หาผลคูณเฉพาะตัวหารเฉพาะ (Unique Prime Factors Product)

โจทย์: หาผลคูณของ Unique Prime Factors ของ n

ตัวอย่าง: 68 = 2² × 17 → Unique primes: 2, 17 → Product = 34

ตัวอย่างโค้ด (Optimized)

public class Demo {
    public static long uniquePrimeFactorsProduct(int n) {
        long product = 1;
        
        // Factor 2
        if (n % 2 == 0) {
            product *= 2;
            while (n % 2 == 0) n /= 2;
        }
        
        // Odd factors
        for (int p = 3; p * p <= n; p += 2) {
            if (n % p == 0) {
                product *= p;
                while (n % p == 0) n /= p;
            }
        }
        
        // Remaining prime > sqrt(n)
        if (n > 1) {
            product *= n;
        }
        
        return product;
    }
    
    public static void main(String[] args) {
        int n = 68;
        System.out.println("n = " + n);
        System.out.println("Unique prime factors product = " + uniquePrimeFactorsProduct(n));
    }
}

ผลลัพธ์

n = 68
Unique prime factors product = 34

คำอธิบาย: หา prime factors โดย trial division จน √n ถ้าเจ้า factor ให้คูณเข้า product แล้ว divide n ด้วย factor นั้นจนหมด (เอา unique factor แค่ครั้งเดียว)

Complexity

• Time: O(√n) - trial division
• Space: O(1)
• Optimization: Pre-compute primes ด้วย Sieve of Eratosthenes สำหรับหลาย query

ขยาย: รองรับ n ใหญ่ (BigInteger)

import java.math.BigInteger;

public static BigInteger uniquePrimeFactorsProductBig(BigInteger n) {
    BigInteger product = BigInteger.ONE;
    BigInteger two = BigInteger.valueOf(2);
    
    if (n.mod(two).equals(BigInteger.ZERO)) {
        product = product.multiply(two);
        while (n.mod(two).equals(BigInteger.ZERO)) n = n.divide(two);
    }
    
    for (BigInteger p = BigInteger.valueOf(3); p.multiply(p).compareTo(n) <= 0; p = p.add(two)) {
        if (n.mod(p).equals(BigInteger.ZERO)) {
            product = product.multiply(p);
            while (n.mod(p).equals(BigInteger.ZERO)) n = n.divide(p);
        }
    }
    
    if (n.compareTo(BigInteger.ONE) > 0) {
        product = product.multiply(n);
    }
    return product;
}