Number of primes less than N

Created:04 Feb 2020 20:33:40 , in  Maths

In this article I look at how to find all prime numbers below a certain positive number N, as well as their sum. We do not know how primes are distributed. There is no function, which reliably finds all primes less then a large natural number. However, we do known an algorithm, which finds prime numbers efficiently for such a number. The algorithm is called Sieve of Eratosthenes (You might want to see who Eratosthenes was). This article provides an implementation of the sieve.

When I looked at finding prime numbers using Sieve of Eratosthenes, the problem did not seem too difficult to solve and the algorithm to implement. However, a working solution took a couple of attempts, and proved extremely inefficient. In fact it was so slow, that finding prime numbers less than 2 000 000 turned out to be a several hours long affair. So, i looked at the problem again. The result of the closer look is another, way more efficient implementation of Sieve of Eratosthenes. The PHP code finds all the prime numbers below 2 000 000 in a few seconds and primes below 20 000 000 in well below a minute, which is good enough for my purposes.

Implementation of Sieve of Eratosthenes in PHP

Below is my implementation of Sieve of Eratosthenes for finding prime numbers.

/** 
  Class: SWWWPrimes 
    contains implementation of Sieve of Eratosthenes algorithm in PHP
  Author: S.Wojnowski
  Licence: GNU  
*/
class SWWWPrimes{

  /**
   *  Sieve($max[,$exclusive])
   *  Arguments: 
   *     max - int - maximum number used for scanning for primes
   *     exclusive - bool - if max is a prime itself it will not be included in the result  
   *  Return value: 
   *     array - array of primes
   */
  public static function sieve($max,$exclusive = true){
    // there are no primes below 2
    if($max < 2){
      return 0;
    }

    // create a suitable array
    $numbers = range(2,$max);
    // start index
    $i = 0;
    // number of items in $numbers
    $count = count($numbers); 
    // value of last value in $numbers
    $last = $count + 1 ;

    // remove non-primes from $numbers
    while(($i + 2) * ($i + 2) <= $last){

      $v = ($i + 2);
      for($k = ($v * $v) - 2 ; $k <= $last-2; $k+=($i+2)){
        if($numbers[$k] % ($v) === 0){
          $numbers[$k] = 0;
        }
      }

      // set i to 2 first then to the next odd number
      if( $v % 2 === 0){
        $i+=1;
      } else {
        $i+=2;
      }
    }

    // by default primes less than $max are returned, remove if inclusive behaviour needed
    if($exclusive && $numbers[$count - 1] === $max){
      $numbers[$count - 1] = 0;
    }
    
    // remove 0s
    return array_filter($numbers,function($n){
      return $n > 0;
    });

    // return array of primes
    return $numbers;
  }
}

List of primes less than N

If N is 10, you obtain all the primes less than 10 as below:

SWWWPrimes::sieve(10);
=> [2,3,5,7]

Sum of primes less than 2 000 000

Finding the sum of prime numbers less than 2 000 000 has been a fairly popular computer programming problem online for a some time.

So, here is how to solve it using the class above:

array_sum(SWWWPrimes::sieve(2000000))
=> 142913828922

Conclusion

Sieve of Eratosthenes algorithm is a very good method for finding prime numbers. This article provides my implementation of the algorithm in PHP programming language. I hope you will find it useful.

Tags:  number theory ,  php