UNIT -II Complex Problem Solving
Points to be covered:
● Factorial Computation
● Power Computation
● Fibonacci Sequence Generation
● Computing n-th Fibonacci number
● Reversing the digits of a number
● Finding Square root of a number
● Smallest Divisor of an integer
● Finding GCD
● Finding LCM
● Generating Prime numbers,
● Computing the prime factor of a number
● Generation of pseudo-random numbers
—----------------------------------------------------------------------------------------------------
● Factorial Computation
A factorial is a function in mathematics with the symbol (!) that multiplies a number (n) by every
number that precedes it. In simpler words, the factorial function says to multiply all the whole
numbers from the chosen number down to one. In more mathematical terms, the factorial of a
number (n!) is equal to n(n-1). For example, if you want to calculate the factorial for four, you
would write:
4! = 4 x 3 x 2 x 1 = 24.
The factorial formula is:
n! = n*(n -1)!
You can follow these steps to solve for a factorial:
1. Determine the number
Determine the number you are finding the factorial of. A factorial has a positive integer and an
exclamation point. For example, if you want to find the factorial for the number eight,
mathematically, it would look like:
8!
2. Write the sequence
Using the factorial formula, you can write out the sequence of numbers that you'll multiply. This
includes the number you are finding the factorial for, the number eight in this example, and all
the numbers descending sequentially from it down to one. Mathematically, it would like this:
CPPS- UNIT-II Complex Problem Solving
n! = n(n-1) =
8(8 − 1)(8 − 2)(8 − 3)(8 − 4)(8 − 5)(8 − 6)(8 − 7)
3. Multiply the numbers
Once you have the sequence of numbers written down, you can multiply
them together. If you multiply all the numbers in this example, 8 ∗ 7 ∗ 6 ∗ 5
∗ 4 ∗ 3 ∗ 2 ∗ 1, you will get a final answer of 40,320. Mathematically, it
looks like this:
n! = n(n-1) =
8(8 − 1)(8 − 2)(8 − 3)(8 − 4)(8 − 5)(8 − 6)(8 − 7) =
8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40,320
You can also compute a factorial using a scientific calculator. The calculator should have a
button with the "x!" sign. Type in the number you want to find the factorial for, in this case, the
number eight, and then push the "x!" button. The calculator should give you the same answer,
40,320.
There are many ways to write the factorial program in c language. Let's see the 2 ways to write
the factorial program.
○ Factorial Program using loop
○ Factorial Program using recursion
Factorial Program using loop
Let's see the factorial Program using loop.
#include<stdio.h>
int main()
{
int i,fact=1,number;
printf("Enter a number: ");
scanf("%d",&number);
for(i=1;i<=number;i++){
fact=fact*i;
}
printf("Factorial of %d is: %d",number,fact);
return 0;
}
Output:
CPPS- UNIT-II Complex Problem Solving
Enter a number: 5
Factorial of 5 is: 120
Factorial Program using recursion in C
Let's see the factorial program in c using recursion.
#include<stdio.h>
long factorial(int n)
{
if (n == 0)
return 1;
else
return(n * factorial(n-1));
}
void main()
{
int number;
long fact;
printf("Enter a number: ");
scanf("%d", &number);
fact = factorial(number);
printf("Factorial of %d is %ld\n", number, fact);
return 0;
}
Output:
Enter a number: 6
Factorial of 5 is: 720
● Power Computation
To calculate power of a number in C using while loop
● In order to calculate the power of a number using a loop we have to take two inputs from
the user, base and the exponent. We have to initialize a variable named power as 1.
● Power variable stores the final value of the power.
CPPS- UNIT-II Complex Problem Solving
● If the exponent is negative, run a while loop till the value of exponent is less than 0.
C program to calculate Power of a number
The program below takes two integers from the user (a base number and an exponent) and
calculates the power.
For example: In the case of 23
● 2 is the base number
● 3 is the exponent
● And, the power is equal to 2*2*2
Power of a Number Using the while Loop
#include <stdio.h>
int main() {
int base, exp;
long double result = 1.0;
printf("Enter a base number: ");
scanf("%d", &base);
printf("Enter an exponent: ");
scanf("%d", &exp);
while (exp != 0) {
result *= base;
--exp;
printf("Answer = %.0Lf", result);
return 0;
CPPS- UNIT-II Complex Problem Solving
}
OUTPUT:
Enter a base number: 3
Enter an exponent: 4
Answer = 81
We can also use the pow() function to calculate the power of a number.
#include <math.h>
#include <stdio.h>
int main() {
double base, exp, result;
printf("Enter a base number: ");
scanf("%lf", &base);
printf("Enter an exponent: ");
scanf("%lf", &exp);
// calculates the power
result = pow(base, exp);
printf("%.1lf^%.1lf = %.2lf", base, exp, result);
return 0;
Enter a base number: 2.3
Enter an exponent: 4.5
2.3^4.5 = 42.44
● Fibonacci Sequence Generation
CPPS- UNIT-II Complex Problem Solving
Fibonacci sequence is a series of numbers where each number is the sum of the two numbers that
come before it. It follows the rule that each number is equal to the sum of the preceding two
numbers. The numbers in the Fibonacci sequence are known as Fibonacci numbers and are
usually represented by the symbol Fₙ. Fibonacci sequence numbers start with the following 14
integers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233.
Nth Fibonacci Number
Given a positive integer n, the task is to find the nth Fibonacci number.
The Fibonacci sequence is a sequence where the next term is the sum of the previous two terms.
The first two terms of the Fibonacci sequence are 0 followed by 1. The Fibonacci sequence: 0, 1,
1, 2, 3, 5, 8, 13, 21
Example:
Input: n = 2
Output: 1
Explanation: 1 is the 2nd number of Fibonacci series.
Input: n = 5
Output: 5
Explanation: 5 is the 5th number of Fibonacci series.
Fibonacci Sequence Formula
Fibonacci formula is used to find the nth term of the sequence when its first and second terms
are given.
The nth term of the Fibonacci Sequence is represented as Fn. It is given by the following
recursive formula,
Fn = Fn-1 + Fn-2
where,
● n>1
● First term is 0 i.e., F0 = 0
● Second term is 1 i.e., F1 = 1
CPPS- UNIT-II Complex Problem Solving
Using this formula, we can easily find the various terms of the Fibonacci Sequence.
Suppose we have to find the 3rd term of this Sequence then we would require the 2nd and
the 1st term according to the given formula, then the 3rd term is calculated as,
F3 = F2 + F1 = 1 + 0 = 1
Thus, the third term in the Fibonacci Sequence is 1, and similarly, the next terms of the
sequence can also be found as,
● F4 = F3 + F2 = 1 + 1 = 2
● F5 = F4 + F3 = 2 + 1 = 3 and so on.
Calculating the Fibonacci Sequence
Fibonacci sequence is a series of numbers in which each number (after the first two) is the sum
of the two preceding ones. The sequence typically starts with 0 and 1.
Steps to Calculate the Fibonacci Sequence
Step 1: Start with Initial Conditions:
● F0 = 0
● F1 = 1
Step 2: Use Fibonacci Sequence Formula
For n ≥ 2n, calculate each Fibonacci number using the formula Fn = Fn-1 +
Fn-2
Thus, using the formula added above one can easily find the Fibonacci sequence up to infinity,
list of first 20 Fibonacci sequence is added below:
List of Fibonacci sequence
Terms of Fibonacci Sequence
CPPS- UNIT-II Complex Problem Solving
F0 = 0 F10 = 45
F1 = 1 F11 = 89
F2 = 1 F12 = 134
F3 = 2 F13 = 233
F4 = 3 F14 = 377
F5 = 5 F15 = 610
F6 = 8 F16 = 987
F7 = 13 F17 = 1597
CPPS- UNIT-II Complex Problem Solving
F8 = 21 F18 = 2584
F9 = 34 F19 = 4181
Below is the first 20 Fibonacci Sequence List.Fibonacci Sequences have infinite terms.
● By closely observing the table we can say that Fn = Fn-1 + Fn-2 for every n > 1.
● Reverse digits of a number
Examples :
Input : num = 12345
Output: 54321
Input : num = 876
Output: 678
CPPS- UNIT-II Complex Problem Solving
CPPS- UNIT-II Complex Problem Solving
ITERATIVE WAY
Algorithm:
Input: num
(1) Initialize rev_num = 0
(2) Loop while num > 0
(a) Multiply rev_num by 10 and add remainder of num
divide by 10 to rev_num
rev_num = rev_num*10 + num%10;
(b) Divide num by 10
(3) Return rev_num
Example:
num = 4562
rev_num = 0
rev_num = rev_num *10 + num%10 = 2
num = num/10 = 456
rev_num = rev_num *10 + num%10 = 20 + 6 = 26
num = num/10 = 45
rev_num = rev_num *10 + num%10 = 260 + 5 = 265
num = num/10 = 4
rev_num = rev_num *10 + num%10 = 2650 + 4 = 2654
num = num/10 = 0
● Finding Square root of a number
Given an integer X, find its square root. If X is not a perfect square, then
return floor(√x).
Examples :
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2.
CPPS- UNIT-II Complex Problem Solving
Input: x = 11
Output: 3
Explanation: The square root of 11 lies in between 3 and 4 so floor of the square root is 3.
Naive Approach: To find the floor of the square root, try with all-natural numbers starting from
1. Continue incrementing the number until the square of that number is greater than the given
number.
Follow the steps below to implement the above idea
1. Create a variable (counter) i and take care of some base cases, (i.e when the given
number is 0 or 1).
2. Run a loop until i*i <= n, where n is the given number. Increment i by 1.
3. The floor of the square root of the number is i – 1
Below is the implementation of the above approach:
Example 1:
#include <stdio.h>
// Returns floor of square root of x
int floorSqrt(int x)
{
// Base cases
if (x == 0 || x == 1)
return x;
// Starting from 1, try all numbers until
// i*i is greater than or equal to x.
int i = 1, result = 1;
while (result <= x) {
i++;
result = i * i;
CPPS- UNIT-II Complex Problem Solving
}
return i - 1;
}
// Driver program
int main()
{
int x = 11;
printf("%d\n", floorSqrt(x));
return 0;
}
// code is contributed by lalith kumar.g
Output
3
Example 2:
/* Display the square root of a number without using the sqrt() function in C. */
#include <stdio.h>
#include <conio.h>
int main()
{
// declaration of the variables
int num;
float sqrt, temp;
printf (" Enter a number to get the square root: ");
scanf (" %d", &num);
// divide the given number by 2 and store into sqrt
sqrt = num / 2;
temp = 0;
// use while loop to continuously checks the sqrt is not equal to the temp
while (sqrt != temp) // Initially temp is 0 and sqrt = num
{
temp = sqrt; // assign sqrt to temp
CPPS- UNIT-II Complex Problem Solving
sqrt = ( num / temp + temp) / 2;
}
printf (" \n The square root of %d is %f", num, sqrt);
return 0;
}
Test it Now
Output:
Enter a number to get the square root: 2
The square root of 2 is 1.414214
In the above program, we input a number from the user which we find the square root. So, first,
we divide the given number by 2 and store it in the sqrt variable. After that, we initialize temp
with 0. And then use the while loop that continuously iterates and checks sqrt is not equal to the
temp, and on each iteration, it assigns the sqrt value to temp, and the sqrt gets a new value by
solving the logic (num/temp + temp) /2; And then prints the square root of 2 is 1.414214.
For More examples: https://www.javatpoint.com/square-root-in-c
● Smallest Divisor of an Integer
Given an integer n devise an algorithm that will find its smallest exact divisor other than one.
All even numbers are divisible by 2. it follows that if the number is not divisible by 2 it will
not be divisible by 4,6,8,10,..... And So if the number we are testing is odd, we should
consider odd numbers as potential smallest divisor candidates.
The overall algorithm can be written as:
1. If the number 'n' is even, then the smallest divisor is 2 else
1. Compute the square root r of n,
2. while no exact divisor less than square root of n do (b.1) test next divisor in
sequence 3, 5, 7, ...
Algorithm Description
1. Establish 'n' the integer whose smallest divisor is required.
2. if 'n' is not odd then return 2 as the smallest divisor else
1. Compute 'r' the square root of 'n',
2. initialize divisor 'd' to 3,
CPPS- UNIT-II Complex Problem Solving
3. while not an exact divisor and square root limit not reached do (c.1) generate next
number in odd sequence d,
4. if current odd value d is an exact divisor, then divide it as the exact divisor of 'n'
else
return 1 as the smallest divisor of 'n'.
Given a number N, find the smallest prime divisor of N.
Examples:
Input: 25
Output: 5
Input: 31
Output: 31
Approach:
● Check if the number is divisible by 2 or not.
● Iterate from i = 3 to sqrt(N) and make a jump of 2.
● If any of the numbers divide N then it is the smallest prime divisor.
● If none of them divide, then N is the answer.
#include<stdio.h>
int main(){
int m, n =27;
m=smallestDivisor(n);
printf("\n %d",m);
return 0;
}
// Function to find the smallest divisor
int smallestDivisor(int n)
{
// if divisible by 2
if (n % 2 == 0)
CPPS- UNIT-II Complex Problem Solving
return 2;
// iterate from 3 to sqrt(n)
for (int i = 3; i * i <= n; i += 2) {
if (n % i == 0)
return i;
}
return n;
}
● Greatest Common Divisor of Two Integers
Given two positive non-zero integers n and m design an algorithm for finding their greatest
common divisor.
The gcd of two integers is the largest integer that will divide exactly into the two integers
with no remainder. We can build up to the common divisor of the two integers by
considering an exact divisor of a single integer. An exact divisor of a number is another
smaller number that divides the original number up into a set of equal parts.
The gcd of two numbers cannot be bigger than the smaller of the two numbers.
Next point is how to continue when the smaller of the two numbers n and m is not their
gcd The basic strategy for computing the gcd of two numbers:
1. Divide the larger of two numbers by the smaller number.
2. if the smaller number exactly divides into larger number then the smaller
number is the gcd
else
remove from the larger number the part common to the smaller number and repeat the
whole procedure with the new pair of numbers.
Terminating the gcd mechanism can be detected by there being no remainder after mod
function
r:= n mod m
if r is zero then m is the gcd,
else
while gcd not found do
1. get remainder by dividing larger integer by the smaller integer;
2. let the smaller integer assume the role of the larger integer;
3. let the remainder assume the role of the smaller integer. repeat the
same process until zero remainder.
CPPS- UNIT-II Complex Problem Solving
#include <stdio.h>
int main()
{
int n1, n2, i, gcd;
printf("Enter two integers: ");
scanf("%d %d", &n1, &n2);
for(i=1; i <= n1 && i <= n2; ++i)
{
// Checks if i is factor of both integers
if(n1%i==0 && n2%i==0)
gcd = i;
}
printf("G.C.D of %d and %d is %d", n1, n2, gcd);
return 0;
}
Applications:
Reducing a fraction to its lowest terms.
LCM Calculation Using GCD
We can also find the LCM of two numbers num1 and num2 using their GCD:
LCM = (num1 * num2) / GCD
Learn how to find the GCD of two numbers in C programming before finding the LCM with this
method.
#include <stdio.h>
int main() {
int n1, n2, i, gcd, lcm;
printf("Enter two positive integers: ");
scanf("%d %d", &n1, &n2);
// loop to find the GCD
for (i = 1; i <= n1 && i <= n2; ++i) {
// check if i is a factor of both integers
if (n1 % i == 0 && n2 % i == 0)
CPPS- UNIT-II Complex Problem Solving
gcd = i;
}
lcm = (n1 * n2) / gcd;
printf("The LCM of two numbers %d and %d is %d.", n1, n2, lcm);
return 0;
}
OUTPUT:
Enter two positive integers:120
The LCM of two numbers 72 and 120 is 360.
● Generating Prime numbers
Prime numbers are positive integers greater than 1 that have no divisors other than 1 and
themselves. In this article, we will learn to generate and display all prime numbers from 1 to N in
C programming language.
C Program to Print Prime Numbers From 1 to N
Algorithm
● Check every number from 1 to N whether it is prime by using isPrime() function.
● In isPrime() Function,
○ Iterate from 2 to sqrt(N) and check if the number is divisible by
any of the values other than itself.
○ If it is divisible by any number, it means the number is not prime,
return false.
CPPS- UNIT-II Complex Problem Solving
○ If it is not divisible by any number, it means the number is prime,
return true.
● If isPrime() returns true, print the number.
● Else continue.
#include <stdbool.h>
#include <stdio.h>
#include <math.h>
int main()
{
int N = 50;
// Check every number from 1 to N
for (int i = 1; i <= N; i++) {
if (isPrime(i)) {
printf("%d ", i);
}
}
return 0;
}
bool isPrime(int n)
{
// 0 and 1 are not prime numbers
if (n == 1 || n == 0)
return false;
// Check for divisibility from 2 to sqrt(n)
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0)
return false;
}
return true;
}
Output
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
CPPS- UNIT-II Complex Problem Solving
