As the name indicates, the prime factors of a given number are its factors that are also prime numbers, e.g., prime factors of 30 are 2, 3 and 5 but not 1, 6, 10, 15 and 30. One or more prime factors of a given number may repeat, e. g., prime factors of 120 are 2, 2, 2, 3 and 5.
To print all occurrences of a prime factor (say divisor) in given number num, use the while loop.
The statements within this loop are executed repeatedly as long as num % divisor is zero, i. e., divisor is a factor of num. Within the loop, first print the divisor as a factor and then remove it from num. Note that if divisor is not a factor of num, nothing happens in the loop.
To print all prime factors of a given number num, we can embed this code in another loop that tests the values of divisor from 2 to n-1. Within this loop, we can first test whether divisor is a prime number or not and if it is, separate all its occurrences from num using the while loop given above. Note that when all the prime factors in a given number are printed and removed, the value of num will be 1. Thus, the outer loop should continue as long as the value of num is greater than 1. A straightforward algorithm that uses this approach is given below.
/* Determine prime factors of a given number */
#include <stdio.h>
void main ()
{
int num, divisor; /* number and divisor */
clrscr();
printf("Enter a number: ");
scanf ("%d", &num);
/* determine and print factors */
printf("Prime factors: ");
divisor = 2;
while (num > 1)
{
while (num % divisor == 0)
{
printf("%d ", divisor); /* divisor is a factor, print it */
num /= divisor; /* remove the factor from num */
}
divisor++;
}
getch();
}
Dinesh Thakur holds an B.SC (Computer Science), MCSE, MCDBA, CCNA, CCNP, A+, SCJP certifications. Dinesh authors the hugely popular Computer Notes blog. Where he writes how-to guides around Computer fundamental , computer software, Computer programming, and web apps. For any type of query or something that you think is missing, please feel free to Contact us.
Related Articles
Basic Courses
Advance Courses