C program to find all prime factors of a number

Prime factorization is a fundamental concept in number theory and various applications in computer science and mathematics. It involves expressing a number as a product of its prime factors. In this article, we will discuss how to write a C program to find all prime factors of a given number.

Understanding Prime Factors

Prime factors of a number are the prime numbers that divide the number exactly, without leaving a remainder. For example, the prime factors of 28 are 2 and 7, since 28 = 2^2 x 7.

Steps to Find Prime Factors

To find the prime factors of a given number n, we can follow these steps:

1. Divide by 2: Continuously divide the number by 2 until it is odd.
2. Check for Odd Factors: Starting from 3, check each odd number up to the square root of the number. If an odd number divides the number, it is a prime factor.
3. Handle the Remaining Number: If the remaining number is greater than 2, it is also a prime factor.

Write a C program to find all prime factors of a number

Here is the C program that implements the above logic:

#include <stdio.h>
#include <math.h>

int main() {
    int n;

    // Input the number from the user
    printf("Enter a number: ");
    scanf("%d", &n);

    // Print the prime factors
    printf("Prime factors of %d are: ", n);

    // Print the number of 2s that divide n
    while (n % 2 == 0) {
        printf("%d ", 2);
        n /= 2;
    }

    // n must be odd at this point. Start from 3 and check all odd numbers.
    for (int i = 3; i <= sqrt(n); i += 2) {
        // While i divides n, print i and divide n
        while (n % i == 0) {
            printf("%d ", i);
            n /= i;
        }
    }

    // This condition is to check if n is a prime number greater than 2
    if (n > 2) {
        printf("%d ", n);
    }

    return 0;
}

Output

Enter a number: 28
Prime factors of 28 are: 2 2 7

Explanation of the Code

1. Input the Number: The program prompts the user to input a number, which is stored in the variable n.
2. Print the Prime Factors:
   • Divide by 2: The while loop continuously divides n by 2 and prints 2 each time until n is odd. This handles the factor 2 separately.
   • Check for Odd Factors: The for loop starts from 3 and checks all odd numbers up to the square root of n. If n is divisible by an odd number i, it prints i and divides n by i until n is no longer divisible by i.
   • Remaining Prime Factor: If n is still greater than 2 after the loop, it means n itself is a prime factor and is printed.