Prime factorization in C

 Prime factorization:    

It is mathematical process which has a product of its prime factors. For example, let us consider 48.

Eg: 48 =2 x 2 x 2 x 2 x 3

The algorithm is given below…

Algorithm:

• ·       First, Start with the smallest prime number. Let it 2.
• ·       Next, divide the number by the prime until it is divisible.
• ·       Try next prime for dividing the number.
• ·       Repeat the process until the number becomes 1.

Program implementation:

• ·       First, create a function prime_Factorization() with the input of no.
• ·       It finds the number is divisible by 2 or not. If yes, it repeats the process until the number becomes odd.
• ·       The odd number is checked for its prime division until, it becomes 1.
• ·       The main() function, gets the input number from user. It calls the prime_ Factorization() function.
• ·       Receives the output from the function and prints it in the output screen.

The program is as follows…

C Program:

#include <stdio.h>

void prime_Factorization(int no) {

    printf("Prime factors of %d are: ", no);

    // First, Divide by 2 until odd

    while (no % 2 == 0) {

        printf("2 ");

        no /= 2;

    }

    // let us Check for odd factors from 3 onwards

    for (int i = 3; i * i <= no; i += 2) {

        while (no % i == 0) {

            printf("%d ", i);

            no /= i;

        }

    }

    // If n is a prime number greater than 2

    if (no > 2)

        printf("%d", no);

}

int main() {

    int number;

    printf("Enter a number: ");

    scanf("%d", &number);

    prime_Factorization(number);

    return 0;

}

Compile and run the program to get the output.

Enter a number: 63

Prime factors of 63 are: 3 3 7

Hope, this concept is useful to you. If you need many more concepts like these, follow this blog. Keep coding!!!