PHP ตรวจสอบจำนวนเฉพาะ (Prime Number)

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

<?php
function check_prime($num) {
    if ($num == 1) return 0;
    for ($i = 2; $i <= $num / 2; $i++) {
        if ($num % $i == 0) return 0;
    }
    return 1;
}

$num = 47;
$flag_val = check_prime($num);
if ($flag_val == 1) echo "It is a prime number";
else echo "It is a non-prime number";
?>

ผลลัพธ์

It is a prime number

คำอธิบาย

• 1 ไม่ใช่ Prime
• ตรวจสอบ Divisors จาก 2 ถึง N/2
• เจอ Divisor → ไม่ใช่ Prime (Return 0)
• ไม่เจอ → เป็น Prime (Return 1)

Optimization: Check עד √n

ไม่ต้องเช็คถึง N/2 แค่ √n พอ เพราะถ้า a×b=n และ a>√n แล้ว b<√n จะเจอแล้ว

<?php
function check_prime_optimized($num) {
    if ($num < 2) return false;
    if ($num == 2) return true;
    if ($num % 2 == 0) return false;
    
    for ($i = 3; $i <= sqrt($num); $i += 2) {
        if ($num % $i == 0) return false;
    }
    return true;
}

// Test
for ($i = 1; $i <= 50; $i++) {
    if (check_prime_optimized($i)) echo "$i ";
}
?>

ผลลัพธ์

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 

Advanced: Sieve of Eratosthenes (หลาย Primes)

<?php
function sieve($n) {
    $isPrime = array_fill(0, $n + 1, true);
    $isPrime[0] = $isPrime[1] = false;
    
    for ($i = 2; $i * $i <= $n; $i++) {
        if ($isPrime[$i]) {
            for ($j = $i * $i; $j <= $n; $j += $i) {
                $isPrime[$j] = false;
            }
        }
    }
    return array_keys(array_filter($isPrime));
}

print_r(sieve(50));
?>

Miller-Rabin (Large Numbers)

สำหรับเลขใหญ่มาก (Cryptography) ใช้ Probabilistic Primality Test