![Number of primes less than N Number of primes less than N](https://swww.com.pl/media/img/post/63_head.jpg)
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](https://swww.com.pl/media/img/gravatar_110.png)
Author of the this article - Sylwester Wojnowski - is a sWWW web developer. He has been writing computer code for the websites and web applications since 1998.
Copyrights
©Copyright, 2024 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://swww.com.pl//main/index/number-of-primes-less-than-n
Add Comment