C Program for efficiently print all prime factors of a given number?

In this section, we will see how we can get all the prime factors of a number in an efficient way. There is a number say n = 1092, we have to get all prime factors of this. The prime factors of 1092 are 2, 2, 3, 7, 13. To solve this problem, we have to follow this rule −

• When the number is divisible by 2, then print 2, and divide the number by 2 repeatedly.

• Now the number must be odd. Now starting from 3 to square root of the number, if the number is divisible by current value, then print, and change the number by divide it with the current number then continue.

Let us see the algorithm to get a better idea.

Algorithm

printPrimeFactors(n)

begin    while n is divisible by 2, do       print 2       n := n / 2    done    for i := 3 to √?, increase i by 2, do       while n is divisible by i, do          print i          n := n / i       done    done    if n > 2, then       print n    end if end

Example

#include<stdio.h> #include<math.h> void primeFactors(int n) {    int i;    while(n % 2 == 0) {       printf("%d, ", 2);       n = n/2; //reduce n by dividing this by 2    }    for(i = 3; i <= sqrt(n); i=i+2){ //i will increase by 2, to get only odd numbers       while(n % i == 0) {          printf("%d, ", i);          n = n/i;       }    }    if(n > 2) {       printf("%d, ", n);    } } main() {    int n;    printf("Enter a number: ");    scanf("%d", &n);    primeFactors(n); }

Output

Enter a number: 24024 2, 2, 2, 3, 7, 11, 13,