जावा प्रोग्राम: संख्या के गुणनखंडों का न्यूनतम योग

उदाहरण

public class Demo { 
    static int minimumSum(int num) { 
        int mySum = 0; 
        for (int i = 2; i * i <= num; i++) { 
            while (num % i == 0) { 
                mySum += i; 
                num /= i; 
            } 
        } 
        mySum += num; 
        return mySum; 
    } 
    
    public static void main(String[] args) { 
        int num = 350; 
        System.out.println("संख्या के गुणनखंडों का न्यूनतम योग है: "); 
        System.out.println(minimumSum(num)); 
    } 
}

आउटपुट

संख्या के गुणनखंडों का न्यूनतम योग है 19

व्याख्या: Demo क्लास में 'minimumSum' नामक एक स्टेटिक फंक्शन होता है, जो योग को 0 से आरंभ करता है, और संख्या के माध्यम से पुनरावृति करता है और उस विशिष्ट संख्या के सभी गुणनखंडों से न्यूनतम योग ढूंढता है। मुख्य फंक्शन में, संख्या का मान परिभाषित किया जाता है, और इस संख्या को पैरामीटर के रूप में पास करके फंक्शन को कॉल किया जाता है। प्रासंगिक संदेश कंसोल पर प्रदर्शित होता है।

समस्या समझ:

"गुणनखंडों का न्यूनतम योग" का अर्थ है: संख्या को गुणनखंडों में विघटित करें (जरूरी नहीं कि अभाज्य) ताकि उनका योग न्यूनतम हो।

लेकिन दिया गया एल्गोरिदम वास्तव में अभाज्य गुणनखंडों का योग गणना करता है!

350 के लिए सत्यापन:

350 = 2 × 5² × 7
अभाज्य गुणनखंड: 2, 5, 5, 7
योग = 2 + 5 + 5 + 7 = 19 ✓

स्पष्टीकरण:

किसी संख्या को गुणनखंडों में विभाजित करने पर, अभाज्य गुणनखंड सबसे छोटा योग देते हैं
क्योंकि: ab ≥ a + b जब a,b ≥ 2 (उदाहरण: 6 = 2×3, योग=5 < 6)
इसलिए पूर्ण अभाज्य गुणनखंडन न्यूनतम योग देता है

सामान्य समाधान:

public static int minFactorSum(int n) {
    int sum = 0;
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            sum += i;
            n /= i;
        }
    }
    if (n > 1) sum += n;  // शेष अभाज्य गुणनखंड
    return sum;
}

उदाहरण:

n=12: 2+2+3=7 (गुणनखंड: 3×4=7, 2×6=8, 12=12)
n=16: 2+2+2+2=8 (गुणनखंड: 4×4=8, 2×8=10, 16=16)
n=17: 17 (अभाज्य)