Number of primes less than N

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 


Author, Copyright and citation

Author

Sylwester Wojnowski

Author of the above article, Sylwester Wojnowski, is sWWW admin and owner.He enjoys doing Maths and studying algorithms, writing code in scripting and command languages, Thrash Metal music and playing electric guitar.

Copyrights

©Copyright, 2020 Sylwester Wojnowski. This article may not be reproduced or published as a whole or in parts without permission from the author. If you share it, please give author credit and do not remove embedded links.

Computer code, if present in the article, is excluded from the above and licensed under GPLv3.

Citation

Cite this article as:

Wojnowski, Sylwester. "Number of primes less than N." From sWWW - Code For The Web . https://wojnowski.net.pl//main/index/number-of-primes-less-than-n