Find total number of divisors of an integer in PHP

Standard

In mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder. Ok, so if you are asked to tell the total number of divisors of 24, it’s easy and the answer is 8 as the number 24 is divided by 1, 2, 3, 4, 6, 8, 12 and 24. Now, how will you implement in PHP programming? You might take the following approach:

Loop through 1 to the number (24 in this case) and check each number that is a divisor of 24 and increment a total counter to print the total number of divisors. Following is the code:

 <?php
 $input = 24;
 $total_divisors = 0;
 for($i=1; $i < $input; $i++) {
   if ($input % $i == 0) $total_divisors++;
 }
 print $total_divisors;
 ?>

Well, this is a good solution, but for small numbers. Think of a number 456789342. If you go by the above method, then the loop will continue to 456789342 times and the execution time of the script will be much more higher and the server will be busy processing the loop. So, the optimized way to do the above is to follow the multiplicative function algorithm.

If prime factorization of n is given by

n = P1 ^ v1 P2 ^ v2 … Pk ^ vk

Then, number of positive divisors of n is

d(n) = (v1 + 1)(v2 + 1)(v3 + 1)

In our example, prime factors of 24 are 2, 3 and 24 = 2 ^ 3 * 3 ^ 1

So, d(24) = (3 +1) * (1+1) = 4 * 2 = 8

Ok, now the code:

<?php
error_reporting(E_ALL);
ini_set("display_errors", 1);
ini_set("log_errors", 0);

class Divisors {
  public $factor = array();

  public function __construct($num) {
    $this->num = $num;
  }

  // count number of divisors of a number
  public function countDivisors() {
    if ($this->num == 1) return 1;

    $this->_primefactors();

    $array_primes = array_count_values($this->factor);
    $divisors = 1;
    foreach($array_primes as $power) {
      $divisors *= ++$power;
    }
    return $divisors;
  }

  // prime factors decomposer
  private function _primefactors() {
    $this->factor = array();
    $run = true;
    while($run && @$this->factor[0] != $this->num) {
      $run = $this->_getFactors();
    }
  }

  // get all factors of the number
  private function _getFactors() {
    if($this->num == 1) {
      return ;
    }
    $root = ceil(sqrt($this->num)) + 1;
    $i = 2;
    while($i <= $root) {
      if($this->num % $i == 0) {
        $this->factor[] = $i;
        $this->num = $this->num / $i;
        return true;
      }
      $i++;
    }
    $this->factor[] = $this->num;
    return false;
  }
} // our class ends here

$example = new Divisors(4567893421);
print $example->countDivisors();
?>

I will be happy to have your feedback. Enjoy coding in PHP!

Advertisements

One thought on “Find total number of divisors of an integer in PHP

  1. “Find Odd divisors summation” This was my today’s interview Question

    Test case
    =======
    Input values 3,1,6,10 answers 11

    I could not answer this but this article helped me to write the code. Thank you very much.

I will be happy to answer your queries

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s