PHP Examples

PHP Program - Find all factors of a Number



Objective: Write a PHP program to find all distinct factors (divisors) of a given natural number. The divisors of few numbers are given below:

 Number: 10
 Divisors: 1 2 5 10

 Number: 15
 Divisors: 1 3 5 15

 Number: 100
 Divisors: 1 2 4 5 10 20 25 50 100 

Method 1: Using iteration

One of the basic approach is to iterate from 1 to n and in each iteration check whether the number divides n. If it divides then print it.

<?php
//function to print all divisors of a number
function printDivisors($n) {
  echo "Divisors of $n are: ";
  for($i = 1; $i <= $n; $i++) {
    if($n%$i == 0)
      echo "$i ";
  }
  echo "\n";
}

printDivisors(10);
printDivisors(50);
printDivisors(100);
?>

The above code will give the following output:

Divisors of 10 are: 1 2 5 10 
Divisors of 50 are: 1 2 5 10 25 50 
Divisors of 100 are: 1 2 4 5 10 20 25 50 100 

Method 2: Optimized Code

Instead of checking the divisibility of the given number from 1 to n, it is checked till square root of n. For a factor larger than square root of n, there must the a smaller factor which is already checked in the range of 1 to square root of n.

<?php
//function to print all divisors of a number
function printDivisors($n) {
  echo "Divisors of $n are: ";
  //loop from 1 to sqrt(n)
  for($i = 1; $i <= sqrt($n); $i++) {
    if($n%$i == 0) {
      if($n/$i == $i)
        echo "$i ";
      else
        echo $i." ".$n/$i." ";
    }
  }
  echo "\n";
}

printDivisors(10);
printDivisors(50);
printDivisors(100);
?>

The above code will give the following output:

Divisors of 10 are: 1 10 2 5 
Divisors of 50 are: 1 50 2 25 5 10 
Divisors of 100 are: 1 100 2 50 4 25 5 20 10 

Method 3: Optimized Code with sorted result

In the previous method, results are produced in a irregular fashion (printed in pairs - small number and large number). The result can be sorted by storing the larger number and print them later on. Consider the example below:

<?php
//function to print all divisors of a number
function printDivisors($n) {
  echo "Divisors of $n are: ";
  
  //creating an array to store larger numbers
  $arr; 
  $j = 0;
  
  //loop from 1 to sqrt(n)
  for($i = 1; $i <= sqrt($n); $i++) {
    if($n%$i == 0) {
      if($n/$i == $i)
        echo "$i ";
      else {
        echo "$i ";
        //storing the large number of a pair
        $arr[$j++] = (int)($n/$i);        
      }
    }
  }

  //printing stored large numbers of pairs
  for ($i = count($arr) - 1; $i >= 0; $i--)
    echo $arr[$i]." ";
  echo "\n";
}

printDivisors(10);
printDivisors(50);
printDivisors(100);
?>

The above code will give the following output:

Divisors of 10 are: 1 2 5 10 
Divisors of 50 are: 1 2 5 10 25 50 
Divisors of 100 are: 1 2 4 5 10 20 25 50 100 

Method 4: Another Optimized Code

To produce the result in sorted order, we can iterate from 1 to square root of n and printing the number which divides n. After that we can iterate back (in reverse order) and printing the quotient of all numbers which divides n.

<?php
//function to print all divisors of a number
function printDivisors($n) {
  echo "Divisors of $n are: ";
  //loop from 1 to sqrt(n)
  $i;
  for($i = 1; $i <= sqrt($n); $i++) {
    if($n%$i == 0) 
      echo "$i ";
    
    //handing perfect squares
    if($n/$i == $i) {
      $i--; 
      break;
    }
  }

  for(; $i >= 1; $i--) {
    if($n%$i == 0) 
      echo $n/$i." ";
  }  
  echo "\n";
}

printDivisors(10);
printDivisors(50);
printDivisors(100);
?>

The above code will give the following output:

Divisors of 10 are: 1 2 5 10 
Divisors of 50 are: 1 2 5 10 25 50 
Divisors of 100 are: 1 2 4 5 10 20 25 50 100