C Program Prime factors of a given number

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();

}