C Program Prime factors of a given number

by Dinesh Thakur Category: Control Structures

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

Search Content

Popular Article