# C program to find all prime factors of a number

Category: C Program

Learn how to write a C program to find all prime factors of a number. This article provides a detailed explanation and complete code implementation to help you understand prime factorization in C.

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.