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!

### Like this:

Like Loading...

*Related*

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