Number of primes between two numbers

Number of primes between two numbers

Created:05 Apr 2017 10:53:55 , in  Maths

Sometimes, especially when dealing with basics of Number Theory, you come across a question that requires stating whether a number is a prime or perhaps finding all the primes there are between two given numbers. In this article I present a tiny PHP class which has methods to answer exactly this sort or questions.

Primes class

The class, Primes, is written in PHP and has only two methods: is_prime and find_primes. Both of them are described in the code fragment below.


/* Class: Primes - find whether number is a prime or find all primes between a pair of numbers
   Author : Sylwester Wojnowski
   WWW : wojnowski.net.pl
    
   Methods: 
     public is_prime($a)
       Description:
         check for primality of $a  
       Parameters: 
         $a positive integer
       Return Value:
         bool - true,false
         
    public find_primes($b, $a=1, $inclusive = true)
       Description:
         find primes between $a and $b
       Parameters: 
         $b positive integer
         $a positive integer - optional - default 1
         $inclusive bool - optional - default true
           if false, $a and $b will not be included in the computation
       Return Value:
         array - array of numbers         
*/

class Primes{
  private $primes = array();
   
  public function __construct(){}
  
  # find factors of number a
  private function factors($a){
    $factors = array();
    $n = 1;
    
    if(!is_int($a)){
      return $factors;
    }
    
    while($n <= $a){
      $b = $a / $n;
      
      if(is_int($b)){
        $factors[] = $b;
      }
      
      $n++;
    }
    
    return $factors;
  }
  
  # find out whether $a is a prime
  public function is_prime($a){
    return count($this -> factors($a)) == 2 ? true : false;  
  }
  
  # find primes between numbers b and a
  public function find_primes($b,$a = 1 , $inclusive = true){
     
    $this -> primes = array();     
        
    if(!$inclusive){
      $a++;
      $b--;
    }
    
    if($a < 1 || $b < 1 || $a > $b ){
      return array();
    }
  
    while($a <= $b){
    
      if($this -> is_prime($a)){
        $this -> primes[] = $a;
      }
 
      $a++;
    }
      
    return $this -> primes;
  }
}

Finding your primes using Primes

Finding out if 37 is a prime:


$pr = new Primes();
$pr->is_prime(37);

Finding all the primes up to 13 inclusive:


$pr->find_primes(13);

Finding all the primes between 90 and 120 inclusive:

        
$pr->find_primes(120,90);

Finding all the primes between 3 and 119 inclusive:


$pr->find_primes(120,2,false);

Finding all the primes less than 120:

    
$pr->find_primes(120,0,false);

Speed of execution

The class is based on rather basic techniques, hence it is not going to be fast for large numbers. Also, the larger the gap between $a and $b the longer it will take to find primes between them.

Final thoughts

I hope you'll find the above piece of code useful. Also, if you found a bug in the code, please let me know.

This post was updated on 25 May 2017 16:18:37

Tags:  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, 2019 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 between two numbers." From sWWW - Code For The Web . https://wojnowski.net.pl//main/index/number-of-primes-between-two-numbers