 # 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.

### Author Author of the above article, Sylwester Wojnowski, enjoys sWWW writing computer code in PHP, JavaScript and BASH, and some other things he wrote more on on the About page of this website.

©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

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

## You might also like

• ### Turning OOP class to graph for better code composition and understanding

MATHS

• ### Using arrow functions for recursive post-order tree traversal

MATHS

• ### Transforming range of variable to 0 to 1 and custom ranges

MATHS

• ### Checking trees for sameness with recursion and spaceship operator in PHP

MATHS

• ### Two indispensable formulas for percentages

MATHS

Allowed BB Code - style tags: [b][/b], [i][/i], [code=text][/code],[code=javascript][/code],[code=php][/code],[code=bash][/code],[code=css][/code],[code=html][/code]

I constent to processing my data given through this form for purposes of a reply by the administrator of this website.