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
Recommended Pages
- PHP Program - To Check Prime Number
- PHP Program - Bubble Sort
- PHP Program - Selection Sort
- PHP Program - Maximum Subarray Sum
- PHP Program - Reverse digits of a given Integer
- PHP Program - Merge Sort
- PHP Program - Shell Sort
- Stack in PHP
- Queue in PHP
- PHP Program - Find LCM of Two Numbers
- PHP Program - To Check Whether a Number is Palindrome or Not
- PHP Program - To Check Whether a String is Palindrome or Not
- PHP Program - Heap Sort
- PHP Program - Quick Sort
- PHP - Swap Two Numbers without using Temporary Variable
- PHP Program - To Check Armstrong Number
- PHP Program - Counting Sort
- PHP Program - Radix Sort
- PHP Program - Find Largest Number among Three Numbers
- PHP Program - Print Floyd's Triangle