Prime Factors of a Number using Recursion - C Program

Problem Question

A positive integer is entered through the keyboard, write a program to obtain the prime factors of the number. Modify the function suitably to obtain the prime factors recursively.

Explanation of Problem

In this program, we need to devise a function that would find the prime factors of a number recursively.

Code

#include <stdio.h>
/**@Title: PrimeFactorsRec.c*
*@Language: ANSI C*
*@Compiler: GNU GCC*
*@IDE: Code::Blocks 13.12*
*@Author: Toxifier*
*@URL: http://letsplaycoding.blogspot.com/*
*@Date: 23-05-2014*
*/

void prime(int x)
{
 int a; //loop counter
 for( a = 2; a <= x; a++ )
 {
  if( x % a == 0 )
  {
   printf("%d ",a);
   prime(x/a);
   break;
  }
 }
}

int main()
{
 int number;
 printf("\n\nEnter a number: ");
 scanf("%d", &number);
 prime(number);
 printf("\n\n");
 system("pause");
 return 0;
}

Explanation of Code

#include <stdio.h> -> This is the step which occurs before compilation starts. The compiler calls the C Preprocessor to include the STDIO(Standard Input Output) header file into the program, thus letting the use of the standard input/output functions like printf() and scanf() which come from STDIO.H

int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. If you use the traditional C, you may use void as the return type. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.

printf() -> This is a standard output function used to print something on the screen. We have to pass a string to this function which will be displayed on user's terminal.

scanf() -> This is the scanf() function which waits for the user to enter certain value using his/her keyboard. We store the user input at the location in memory which is pointed to by the variable whose address is passed to this function.

 for( a = 2; a <= x; a++ )
 {
  if( x % a == 0 )
  {
   printf("%d ",a);
   prime(x/a);
   break;
  }
 }

This is the part of code where the calculation takes place. The for loop, for( a = 2; a <= x; a++ ) keeps incrementing the counter, 'a'. We use it to divide the number that user entered. The if condition, if( x % a == 0 ) checks if the number is divisible by the current value of the counter 'a'. If that is the case, we print the number 'a' and call our function prime recursively, but this time with a value 'x/a' rather than 'x'. With this, we are not stuck in an infinite recursion of printing the same prime factor. Since we keep on dividing the number by the prime factor found in last iteration, we are sure of segregating any multiples of this 'found prime factor'. Hence, we avoid getting the composite factors, since the counter always starts at 2. Thus only prime factors get printed on the screen, with a single space separating each of them.

system("pause") -> This statement is used to pause the program, until user presses a key. This function is not necessary in your program, I use it to see my outputs paused. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Depending on your compiler, this function may or may not work. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.

Output(s)