# C program to find all prime factors of a number

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:

**Divide by 2**: Continuously divide the number by 2 until it is odd.**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.**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

**Input the Number**: The program prompts the user to input a number, which is stored in the variable`n`

.**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.