PHP प्रोग्राम: पहला नेचुरल नंबर जिसका फैक्टोरियल x से विभाज्य हो

फैक्टोरियल विभाज्यता: पहला n जहां n! % x == 0

उदाहरण

<?php
function factorial_num($x_val) {
    $i = 1;
    $fact_num = 4; // बग: हार्डकोडेड 4 से शुरू
    for ($i = 1; $i < $x_val; $i++) {
        $fact_num = $fact_num * $i;
        if ($fact_num % $x_val == 0) {
            break;
        }
    }
    return $i;
}

$x_val = 16;
print_r("The first natural number whose factorial can be divided by 16 is ");
echo factorial_num($x_val);
?>

आउटपुट

The first natural number whose factorial can be divided by 16 is 4

⚠️ कोड में बग

$fact_num = 4 हार्डकोडेड है। सही इनिशियलाइज़ेशन $fact_num = 1 होना चाहिए। संयोग से x=16 के लिए उत्तर 4 ही आता है, लेकिन अन्य इनपुट्स के लिए गलत होगा।

सही इम्प्लीमेंटेशन

<?php
function firstFactorialDivisible(int $x): int {
    if ($x <= 1) return 1;
    
    $factorial = 1;
    for ($i = 1; $i <= $x; $i++) { // अधिकतम x तक (x! हमेशा x से विभाज्य)
        $factorial *= $i;
        if ($factorial % $x == 0) {
            return $i;
        }
    }
    return $x; // फॉलबैक
}

// टेस्ट
$testCases = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 16, 20, 25, 100];
foreach ($testCases as $x) {
    echo "x=$x → n=" . firstFactorialDivisible($x) . "\n";
}
?>

आउटपुट

x=1 → n=1
x=2 → n=2
x=3 → n=3
x=4 → n=4
x=5 → n=5
x=6 → n=3  (3! = 6, 6%6=0)
x=7 → n=7
x=8 → n=4  (4! = 24, 24%8=0)
x=9 → n=6  (6! = 720, 720%9=0)
x=10 → n=5 (5! = 120, 120%10=0)
x=12 → n=4 (4! = 24, 24%12=0)
x=16 → n=6 (6! = 720, 720%16=0) ← मूल कोड ने 4 दिया था (गलत!)
x=20 → n=5
x=25 → n=10
x=100 → n=10

मूल कोड की त्रुटि

x=16 के लिए मूल कोड 4 लौटाता है, लेकिन 4! = 24, 24 % 16 = 8 ≠ 0। सही उत्तर 6 है (6! = 720, 720 % 16 = 0)।

ऑप्टिमाइजेशन: प्राइम फैक्टराइज़ेशन

बड़े x के लिए, फैक्टोरियल की बजाय प्राइम फैक्टराइज़ेशन का उपयोग करें:

function firstFactorialDivisibleFast(int $x): int {
    // x के प्राइम फैक्टर ढूंढें
    // प्रत्येक प्राइम p के लिए, न्यूनतम n ढूंढें जहां n! में p की पर्याप्त पावर हो
    // अधिकतम n लौटाएं
}