Tag: recursion

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

Analyze The Problem Statement

According to problem statement we need to find prime factors of user input positive integer number using iterative logic first, and then modify it and write a recursive logic to obtain the same result.

In our video tutorial we’ll write both iterative as well as recursive logic. This way you can compare the two – both the similarities and differences in the code.

For Example: Prime factors of 24 are 2, 2, 2 and 3.

Related Read:
C Program To Find Prime Factors of a Number

Note:
Both 24 and 35 are not prime numbers, but the factors(2, 3, 5 and 7) we display are prime numbers and multiplying all the prime factors should give the original number.

Video Tutorial: C Program To Find Prime Factors of a Number using Recursion

Source Code: C Program To Find Prime Factors of a Number using Recursion

#include<stdio.h>

void pfactors_rec(int, int);
void pfactors(int);

int main()
{
    int num;

    printf("Enter a positive integer number\n");
    scanf("%d", &num);

    printf("\nPrime Factors of %d without using recursion\n", num);
    pfactors(num);

    printf("\nPrime Factors of %d using recursion\n", num);
    pfactors_rec(num, 2);

    return 0;
}

void pfactors_rec(int num, int count)
{
    if(num < 1)
        return;
    else if(num % count == 0)
    {
      printf("%d\n", count);
      pfactors_rec(num / count, count);
    }
    else
    {
      pfactors_rec(num, count+1);
    }
}

void pfactors(int num)
{
    int count;

    for(count = 2; (num > 1); count++)
    {
        while(num % count == 0)
        {
            printf("%d\n", count);
            num = num / count;
        }
    }
    printf("\n");
}

Output 1:
Enter a positive integer number
24

Prime Factors of 24 without using recursion
2
2
2
3

Prime Factors of 24 using recursion
2
2
2
3

Output 2:
Enter a positive integer number
35

Prime Factors of 35 without using recursion
5
7

Prime Factors of 35 using recursion
5
7

Output 3:
Enter a positive integer number
510

Prime Factors of 510 without using recursion
2
3
5
17

Prime Factors of 510 using recursion
2
3
5
17

Output 4:
Enter a positive integer number
24024

Prime Factors of 24024 without using recursion
2
2
2
3
7
11
13

Prime Factors of 24024 using recursion
2
2
2
3
7
11
13

Output 5:
Enter a positive integer number
315

Prime Factors of 315 without using recursion
3
3
5
7

Prime Factors of 315 using recursion
3
3
5
7

Logic To Find Prime Factors of a Number using Recursion

We pass the user input number and 2 to the recursive function pfactors_rec(). We pass 2 as count value because 2 is the first prime number. So we initialize 2 to count and we change the value of count inside pfactors_rec() function.

Inside pfactors_rec() function
We first write the base condition(i.e., a condition to exit or return from the infinite recursive calls – freeing up the memory stack). We check if num value is less than 1, in that case we return the control back to the calling function.

Inside else if condition we check if the user input number is perfectly divided by 2(initial value of variable count). If true, then we print the value 2 and then divide the number by 2. We keep doing this recursively until num is not perfectly divided by 2.

If 2 can’t perfectly divide the number then, else condition code is executed, where we increment the value of count by 1.

Since inside else if we keep dividing the number by value of count until it perfectly divides the number, the multiples of value of count can not divide the number going further. So only prime numbers can(probably) perfectly divide the value present inside variable num. This is the reason we need not write function to find next prime number and then assign it to count.

Example with output

Since num = 1, base condition gets executed and all the function instances of pfactors_rec() and associated memory gets popped out of the stack and finally the prime factors of the user input number will be left out on the console window.

Logic To Find Prime Factors of a Number using Iterative Logic

Complete logic, code and explanation with example is given at C Program To Find Prime Factors of a Number

Important Note:

If user input number is perfectly divisible by 5, then we iteratively or recursively or repeatedly divide the number by 5, until the number is no longer perfectly divisible by the number 5. That way, going forward, no other numbers which are multiples of 5 can perfectly divide the number.

For Example: If user input number is 24, and you continously divide the number 24 by 2 until 2 doesn’t perfectly divide the number, then no other multiples of 2 can perfectly divide the number.

Step 1:

num = 24, count = 2;

24 % 2 == 0 (True)
24 / 2 = 12;

Step 2:

num = 12, count = 2;

12 % 2 == 0 (True)
12 / 2 = 6;

Step 3:

num = 6, count = 2;

6 % 2 == 0 (True)
6 / 2 = 3;

Step 3:

Now num is reduced to 3, so no other numbers which are multiples of number 2 can perfectly divide the number(which happens to be 3 in this case).

Check steps 1, 2 and 3 for any number. Ultimately, only prime numbers can perfectly divide any number. Take a pen and paper and give it a try.

For list of all c programming interviews / viva question and answers visit: C Programming Interview / Viva Q&A List

For full C programming language free video tutorial list visit:C Programming: Beginner To Advance To Expert