C program to find prime factors of any number

Write a C program to enter any number and find Prime factors of the given number. C program to list all prime factors of a given number. Logic to print prime factors of any given number in C program.

Input any number: 10

Prime factors of 10: 2, 5

Required knowledge

Basic C programming, If else, For loop

What is Prime factor?

Factors of any number that are prime numbers are called as Prime factors of that number. For example: 2 and 5 are the prime factors of 10. Read more about prime factors.

Logic to check prime factors of a given number

Let us learn the logic to find prime factors. I have divided the logic in three simple steps. But before I formally state the logic. It is recommended that you must know below concepts.

• Program to find factors of a number.
• Program to check prime number.

Below is the step by step descriptive logic to find prime factors.

1. Read a number from user. Store it in some variable say num.
2. Run a loop from 2 to num/2, incrementing 1 in each iteration. The loop structure should look like for(i=2; i<=num/2; i++). You may think why loop from 2 to num/2? Because prime number starts from 2 and any factor of a number is always less than n/2.
3. Inside the loop check if i is a factor of num or not. If it is a factor then check it is prime or not. If i is factor and is prime then you got one prime factor of num.

Program to find prime factors of any number

/**
 * C program to find all prime factors of a given number
 */

#include <stdio.h>

int main()
{
    int i, j, num, isPrime;

    /*
     * Read a number from user
     */
    printf("Enter any number to print Prime factors: ");
    scanf("%d", &num);

    printf("All Prime Factors of %d are: \n", num);

    /*
     * Find all Prime factors
     */
    for(i=2; i<=num; i++)
    {
        /*
         * If i is a factor of num
         */
        if(num%i==0)
        {
            /*
             * If i iss Prime or not
             */
            isPrime = 1;
            for(j=2; j<=i/2; j++)
            {
                if(i%j==0)
                {
                    isPrime = 0;
                    break;
                }
            }

            /*
             * If i is Prime factor of num
             */
            if(isPrime==1)
            {
                printf("%d, ", i);
            }
        }
    }

    return 0;
} 

Enter any number to print Prime factors: 15
All Prime Factors of 15 are: 
3, 5, 

Happy coding ;)