# Implementation of Egyptian Fraction using Greedy Algorithm in C++

In this article, we will learn how to implement Egyptian Fraction using a Greedy Algorithm in C++. A positive fraction number can be represented as the sum of unique unit fractions. A fraction is said to be a unit fraction if its numerator is one and the denominator some positive number. For example, 1/8 is said to be a unit fraction.

Some of the examples of Egyptian Fraction are

Egyptian Fraction representation of 5/6 is 2/3 + 1/2.

Egyptian Fraction representation of 8/15 is 1/3 + 1/5.

## Egyptian Fraction using Greedy Algorithm in C++

1. Firstly, get the numerator and denominator of the fraction as n and d respectively.

2. Check the corner when d is equal to zero or n is equal to zero.

3. Check if d is divisible by n then print 1/(d/n).

4. If n is divisible by d then print (n/d).

5. Now compare n with d, if n is greater than d

• print n/d
• recursively call the egyptianFraction() function i.e. egyptianFraction(n%d, d);

6. If d is greater than n

• print d/n + 1
• recursively call the egyptianFraction() function i.e. egyptianFraction(n*x-d, d*x);
```#include <bits/stdc++.h>
using namespace std;
void egyptianFraction(int n, int d){
if (d == 0 || n == 0)
return;
if(d%n == 0){
cout<<"1/"<<d/n;
return;
}
if(n%d == 0){
cout<<n/d;
return;
}
if (n>d){
cout<<n/d<<" + ";
egyptianFraction(n%d, d);
return;
}
int x = d/n+1;
cout<<"1/"<<x<<" + ";
egyptianFraction(n*x-d, d*x);
}
int main(){
int n, d;
cout<<"Enter the numerator of fraction: ";
cin>>n;
cout<<"Enter the denominator of fraction: ";
cin>>d;
cout<<"Egyptian Fraction representation of "<<n<<"/"<<d<<" is"<<endl;
egyptianFraction(n, d);
return 0;
}```

Output

```Enter the numerator of fraction: 2
Enter the denominator of fraction: 3
Egyptian Fraction representation of 2/3 is
1/2 + 1/6

Enter the numerator of fraction: 1
Enter the denominator of fraction: 6
Egyptian Fraction representation of 1/6 is
1/6

Enter the numerator of fraction: 18
Enter the denominator of fraction: 19
Egyptian Fraction representation of 18/19 is
1/2 + 1/3 + 1/9 + 1/342```