Write a Program to find all Prime Factors of number in C

Spread the love
prime-factors-in-c-language-using-loops

Program Description:

We have looked at the Factors of number program, and GCD Program in earlier posts, In today’s post we are going to write a program to calculate all Prime Factors in C language using the Loops. The program should accept a positive number from the user and provide all Prime Factors of the given number.

What are the Prime Factors of a Number?

Prime Factors of a number are the prime numbers multiplied together to make the given number.

So The Prime factors are factors of the original number but the factors must also be prime numbers. ( Prime Factors).

Here are a few examples of Numbers and their Prime Factors.

NumberPrime Factors
702, 5, 7
1002, 5
7893, 263
453, 5

Example Input and Output:

Input:

Enter a Number to calculate Prime Factors: 78

Output:

Prime Factors of 78 are : 2 3 13

Program Pre-Requisites:

It is recommended to know the C Loops and Modulus Operators. Please go through the following articles to learn more about them.

Program to Calculate Prime Factors in C Language Algorithm:

In Nutshell, We need to find all Factors of the given number and then check if the factor is a prime number or not. If the factor is a prime number, Then said factor is a prime factor.

  1. Take input from the user and store it in variable num
  2. Check if the num is less than 1(As the prime numbers start from 2). If so display the error message. Invalid Input, Please try again
  3. Now find all factors of the number num. By checking all numbers from 1 to num (i<=num), which evenly divides the num. If the i evenly divides the num, Then i is Factor of num.
  4. Once we got the Factor, Then we need to check if the factor is a prime Number. To check factor is a prime number, use any of the below methods
  5. If the factor is Prime number, Then display it on the console. Otherwise, go to the next iteration.
  6. The loop continues until the condition i<=num becomes False

Normal Method: Calculate the Prime Factors of a Number in C using While loop:

We are going to use the normal method to check the prime numbers, i.e to check all numbers from the 2 to n/2.

Program Output:

Compile the program using your favorite compiler. We are using the GCC compiler here.

gcc prime-factors-normal.c

The above command generates the executable file named a.out. Run the executable.

Positive number Test Cases:

We are getting the expected output.

prime-factors-of-number-program-output-in-c

Let’s test the negative number Test cases:

As expected, the program is displaying the error message on Invalid numbers like Negative numbers.

Efficient Method – Prime Factors in C using Square root method:

In this method, We are going to calculate the Prime Factors of number using the Square root method.

We are going to use the sqrt function from the math.h header file.

Program Output:

As we used the library function sqrt, We need to pass the -lm (math.h’s is implemented as part of the libm.solibrary) option to GCC.

Otherwise, we get the linking error. Here is an example, Without passing the -lm option.

As you can see from the above output, We got the Linking error. To overcome the linking error, We need to pass the -lm option.

$ gcc prime-factors-2.c -lm

The above command is executed without any error and the executable file a.out is generated.

Run the program.

Generate all Prime Factors in C using For loop:

Let’s re-write the above program using the for loop instead of the while loop.

Program Output:

prime-factors-of-number-program-output-in-c-using-for-loop

Learn More about Prime Factors at :

Venkat

Hi Guys, I am Venkatesh. I am a programmer and an Open Source enthusiast. I write about programming and technology on this blog.

You may also like...

3 Responses

  1. […] C Program to find all Prime Factors of number  […]

  2. […] C Program to find all Prime Factors of number  […]

  3. […] C Program to find all Prime Factors of number  […]

Leave a Reply