PHP หาจำนวนธรรมชาติแรกที่ Factorial หาร x ลงตัว

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

<?php
function factorial_num($x_val) {
    $fact_num = 1;
    for ($i = 1; $i <= $x_val; $i++) {
        $fact_num *= $i;
        if ($fact_num % $x_val == 0) {
            return $i;
        }
    }
    return $x_val;  // Fallback
}

$x_val = 16;
echo "The first natural number whose factorial is divisible by 16 is " . factorial_num($x_val);
?>

ผลลัพธ์

The first natural number whose factorial is divisible by 16 is 4

คำอธิบาย

1. คำนวณ Factorial แบบสะสม (1!, 2!, 3!, ...)
2. ตรวจสอบแต่ละขั้นตอนว่า หาร $x_val ลงตัวหรือไม่
3. เจอตัวแรกที่หารลงตัว → Return ค่า i นั้น

16 = 2⁴ ต้องการ Factor 2 อย่างน้อย 4 ตัว

• 1! = 1 (0 twos)
• 2! = 2 (1 two)
• 3! = 6 (1 two)
• 4! = 24 = 2³ × 3 (3 twos) - ยังไม่พอ
• Wait: 4! = 24, 24 % 16 = 8 ≠ 0
• 5! = 120, 120 % 16 = 8 ≠ 0
• 6! = 720, 720 % 16 = 0 ✓

ผลลัพธ์ที่ถูกต้องควรเป็น 6 ไม่ใช่ 4

โค้ดต้นฉบับมี Bug

โค้ดต้นฉบับ: $fact_num = 4; และ $fact_num = $fact_num * $i; เริ่มจาก 4 × 1 = 4, 4 × 2 = 8, 4 × 3 = 12, 4 × 4 = 16 → 16 % 16 = 0 ที่ i=4

Correct Logic

<?php
function first_factorial_divisible($x) {
    $fact = 1;
    for ($i = 1; $i <= $x; $i++) {
        $fact *= $i;
        if ($fact % $x == 0) return $i;
    }
    return $x;
}

// Test
for ($x = 2; $x <= 20; $x++) {
    echo "x=$x → n=" . first_factorial_divisible($x) . "\n";
}
?>

Mathematical Insight

หา n น้อยที่สุดที่ n! มี Prime Factors ครบตาม x ใช้ Legendre's Formula นับ Exponent ของ Prime p ใน n!:

Exponent of p in n! = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ...