Print All Prime Factors of a Given Number using Trial Division
The simplest method to find prime factors is by trial division. We start from the smallest prime number, 2, and divide the given number as long as it is divisible. We then move to the next prime numbers and repeat the process.
PHP
<?php function primeFactors($n) { // Print the number of 2s // that divide n while ($n % 2 == 0) { echo "2 "; $n = $n / 2; } // n must be odd at this point. // So, we can skip one element // (i.e., we can start from i = 3 // and increment by 2) for ($i = 3; $i <= sqrt($n); $i += 2) { // While i divides n, print i and divide n while ($n % $i == 0) { echo "$i "; $n = $n / $i; } } // This condition is to handle the case // when n is a prime number greater than 2 if ($n > 2) { echo "$n"; } } // Driver code $number = 315; primeFactors($number); ?> |
Output
3 3 5 7
Explanation:
- The function
primeFactorstakes an integer$nas input and prints its prime factors. - First, it prints all the 2s that divide
$n. - Then, it iterates from 3 to the square root of
$n, checking for divisibility by odd numbers (since even numbers have already been checked). - If
$idivides$n, it prints$iand divides$nby$i, repeating this process as long as$idivides$n. - Finally, if
$nis greater than 2, it means$nis a prime number itself, and it is printed.
PHP Program to Print All Prime Factors of a Given Number
Prime factors of a number are the prime numbers that divide the given number exactly. Finding prime factors is a common task in number theory and has applications in cryptography and algorithm design. In this article, we will discuss efficient ways to print all prime factors of a given number in PHP.
Contact Us