Write the following program and run it.
Code:
#include <iostream>
#include <stdio.h>
#include <time.h>
int GCD_Euclid(int x, int y);
int GCD_EuclidRec(int x, int y);
int GCD_Simple(int x, int y);
bool isPrime(int x);
bool isprime_Rec(int x,int z);
using namespace std;
void main(int argc)
{
int x,y;
for(int rep=1; rep<=5; rep++){
srand(time(NULL)*rep);
x= rand()%100;
y= rand()%100;
cout << "GCD of " << x << " and " << y << " is " << GCD_Euclid(x,y) << endl;
cout << "GCD of " << x << " and " << y << " is " << GCD_EuclidRec(x,y) << endl;
cout << "GCD of " << x << " and " << y << " is " << GCD_Simple(x,y) << endl;
cout<<endl;
if(isPrime(x))
cout<<"the number "<<x<<" is prime"<<endl;
else
cout<<"the number "<<x<<" isn't prime"<<endl;
if(isprime_Rec(x,2))
cout<<"the number "<<x<<" is prime"<<endl;
else
cout<<"the number "<<x<<" isn't prime"<<endl;
cout << endl;
}
}
int GCD_Euclid(int x, int y){
while(y!=0){
int r=x%y;
x=y;
y=r;
}
return x;
}
int GCD_EuclidRec(int x, int y)
{
return rand();
}
int GCD_Simple(int x, int y)
{
return rand();
}
bool isPrime (int x)
{
return rand();
}
bool isprime_Rec(int x, int z=2)
{
return rand();
}
Run the program and obtain the output.
Implement the two functions isPrime and isprime_Rec.
Run the program and obtain the output.
Tasks (what to hand in):
Hand in the functions GCD_EuclidRec and GCD_Simple.
Hand in the functions isPrime and isprime_Rec.
Hand in the output of step 3 and 5.
How many steps are needed to find the GCD using the simple algorithm is the value of the first number is q and the second number is d?
If at least one of the two numbers is prime, what is the GCD of the two numbers? Why
