phpeveryday.com

<?php
// list all primes between 2 and some integer ↵
// using the Sieve of Erastothenes
function listPrimes($end) {
  // generate an array of all possible integers
  // between the first prime and the supplied limit
  $sieve = range(2, $end);

  // retrieve the size of the array
  $size = sizeof($sieve);
  // reset internal array pointer to beginning of array
  reset($sieve);

  // iterate over the array
  while (list($key, $val) = each($sieve)) {
    // for each element
    // check if subsequent elements are divisible by it
    // remove them from the array if so
    for ($x=$key+1; $x<$size; $x++) {
      if ($sieve[$x] % $val == 0) {
        unset($sieve[$x]);
      }
    }
  }
  // at the end, elements left in array are primes
  return $sieve;
}

// list all the primes between 2 and 100
// result: "2 3 5 7...83 89 97"
echo implode(" ", listPrimes(100));
?>

A prime number is a number that has only two divisors: itself and 1. Known as the Sieve of Eratosthenes, after the Greek scholar of the same name, it essentially requires you to perform three steps:
1. List all the integers between 2 and some number n.
2. Begin with the fi rst number in the list. Remove all the numbers from the list that are (a) greater than it, and (b) multiples of it.
3. Move to the next available number and repeat the process.

If the remainder is 0 at any stage, it means that the number was fully divisible and, hence, cannot be prime. Here's a function that encapsulates this logic:

<?php
// check if a number is a prime number
function testPrime($num) {
  // divide each number
  // by all numbers lower than it (excluding 1)

  // if even one such operation returns no remainder
  // the number is not a prime
  for ($x=($num-1); $x>1; $x--) {
    if (($num % $x) == 0) {
      return false;
    }
  }
  return true;
}

// test if 9 is prime
// result: "Number is not prime"
echo testPrime(9) ? "Number is prime" : "Number is not prime";
?>

It is easy to write a function that satisfies another common requirement: listing the first n primes by using the testPrime() function described previously. Just take a look at beneath:

<?php
// list first N primes
function getFirstNPrimes($n) {
  // define an empty array to store primes
  $primesArray = array();
  // start with the first prime
  $count = 2;
  
  // sequentially test numbers
  // until the required number of primes is obtained
  while (sizeof($primesArray) < $n) {
    if (testPrime($count)) {
      $primesArray[] = $count;
    }
    $count++;
  }
  
  return $primesArray;
}

// list the first 90 primes
echo implode(" ", getFirstNPrimes(90));
?>