C program to find prime factors of a number

In this post, you will learn how to write the C program to find the prime factors of a number. Before starting the coding part, it should be clear about the prime number and prime factor.

A prime number is a whole number greater than 1, whose only factors are 1 and itself. The prime numbers that divide the given number perfectly are known as the prime factors of that number. Basically, it is finding those prime numbers that multiply together to make the original number. For example, if the input number is 110, then the output should be "2 5 11". And if the input number is 99, then the output should be "3 3 11".

With the help of these two conditions, we can check whether a number is a prime factor of a given number or not.

• The number must be a prime number.
• The number must perfectly divide the given number.

It should also be clear that where we should use the prime factorization of current web technology, when working with large numbers, such as in cryptography, prime factorization is useful. It is also commonly used in mathematical problems to secure public-key encryption systems.

C Program to find prime factors using function

Here is the C program to find prime factors of a number using a function. This program allows the user to enter any positive integer and find the prime factors of that.

// Prime factor program in C
#include<stdio.h>
#include<math.h>

void primeFactors(int num) {
   int i;

   // Print the number of 2s
   // that divide num
   while(num % 2 == 0) {
      printf("%d, ", 2);
      num = num/2;
   }
   // num must be odd at this point
   for(i = 3; i <= sqrt(num); i=i+2){
      // while i divides num,
      // print i and divide num
      while(num % i == 0) {
         printf("%d, ", i);
         num = num/i;
      }
   }
   // Handle the case when num is prime
   // number greater than 2
   if(num > 2) {
      printf("%d, ", num);
   }
}

main() {
   int num;
   printf("Please enter any positive number to find factors : ");
   scanf("%d", &num);
   primeFactors(num);
}

Please enter any positive number to find factors : 110
2, 5, 11,

Please enter any positive number to find factors : 99
3, 3, 11,

In the above example, we have used the for loop and while to find the prime factors. Firstly, we have taken the input from the user and stored it in a variable num. Then, we have applied the while loop, if num is divisible by 2, then print 2 and divide num by 2. After this step, we have applied the for loop from i = 3 to the square root of num. While i divides num, print i and divide num by i. After i fails to divide num, increment i by 2 and continue. Next, we print the num value, if it is greater than 2. Hence, the prime factors are printed with a single-single value.

C Program to find prime factors of a number using a for loop

The given C program finds the prime factors of a number using a for loop. We run the loop from 2 to num/2 as the prime number starts from 2 and increments by 1 in each iteration. Inside the loop, we check if x is a factor of num or not. If it is a factor, then check whether it is prime or not.

#include <stdio.h>
 
int main()
{
  	int x, y, num, isPrime; 
   
  	printf("\n Please enter any positive number to find factors :  ");
  	scanf("%d", &num);
 
  	for (x = 2; x <= num; x++)
   	{
     	if(num % x == 0)
        {
   			isPrime = 1;
			for (y = 2; y <= x/2; y++)
			{
				if(x % y == 0)
				{
					isPrime = 0;
					break;
				}
			} 
			if(isPrime == 1)
			{
				printf("\n %d is a Prime Factor ", x);
			}	          	
		}
   }
  	return 0;
}

Please enter any positive number to find factors :  110
 
2 is a Prime Factor 
5 is a Prime Factor 
11 is a Prime Factor 

C Program to find prime factors of a number using a while loop

The given C program finds the prime factors of a number using a while loop.

/* C Program to Find Prime factors of a Number using While Loop */
 
#include <stdio.h>
 
int main()
{
  	int num, x = 1, y, count; 
 
  	printf("\n Please enter any positive number to find factors :  ");
  	scanf("%d", &num);
 
 	while (x <= num)
   	{
   		count = 0;
    	if(num % x == 0)
      	{
      		y = 1;
      		while(y <= x)
      		{
      			if(x % y == 0)
      			{
      				count++;
				}
				y++;
			}
			if(count == 2)
			{
				printf("\n %d is a Prime Factor ", x);
			} 
      	}
    	x++;
   	}
  	return 0;
}  	
}

Please enter any positive number to find factors :  121

11 is a Prime Factor

Related Articles