Chapter 5,Problem b: Let Us C by Yashawant Kanetkar Solution Manual

Problem Statement:

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.

Solution:

//Ahmad Furqan

//P5.b

#include <iostream>

#include <conio.h>

using namespace std;

bool is_prime(int num)

{

if (num == 2 || num == 3)

return true;

if (num < 2 || num%2==0)  //If number is less than 2 or even its not prime

return false;

//starting from 3 we try dividing by odd numbers,

//since its not even its not divisible by any even number

//we need to go upto num/2

for (int i = 3; i < num / 2; i += 2)

{

if (num%i == 0)

return false;

}

return true;

}

void show_prime_fact_rec(int num)

{

if (is_prime(num)) //if num is prime show it and return since it don't have any factors

{

cout << num << endl;

return;

}

//find smallest prime factor of the number and show it

int i;

for (i = 2; i < num / 2; i++)

{

if (num%i == 0)

{

if (is_prime(i))

break;

}

}

cout << i << endl;

//call function with num divided with lowest prime factor to find other factors

return show_prime_fact_rec(num/i);

}

void main(void)

{

int num;

cout << "Enter a number: ";

cin >> num;

cout << "Prime factors of the number are:" << endl;

show_prime_fact_rec(num);

_getch();

}