How to use Sieve of Eratosthenes In PHP

Using Trial Division Method

The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers to a given limit. It works by iteratively marking the multiples of each prime, starting from 2.

PHP

<?php 
  
function findPrimeNums($n) { 
    $isPrime = array_fill(2, $n, true); 
    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)); 
} 
  
// Driver code 
$start = 10; 
$end = 50; 
  
$primeNums = findPrimeNums($end); 
  
$primeNumsInRange = array_filter($primeNums,  
    function ($num) use ($start, $end) { 
        return $num >= $start && $num <= $end; 
    }); 
  
echo implode(', ', $primeNumsInRange); 
  
?>

Output

11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

PHP Program to Find All Prime Numbers in a Given Interval

Prime numbers are fundamental in the field of mathematics and computer science. A prime number is defined as a natural number greater than 1 and is divisible by only 1 and itself.

In this article, we will explore how to write a PHP program to find all prime numbers within a given interval.