algorithm dealing with GCD_EuclidRec and GCD_Simple

dodo rawash's Avatar, Join Date: Oct 2010
Newbie Member
I am a student who is taking a computer science course in college and have been assigned to write an algorithm for ac++ program. I have no previous programming experience and I am really behind in this class. It seems fairly simple and anyone on here could probably do it with their eyes closed. I have to write an algorithm dealing with GCD_EuclidRec and GCD_Simple (see below) but do not know where to go from there. As you can see its basic fudamentals of c++ but i have no clue what i am doing, any help would be greatly appreciated.

Write the following program and run it.
#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++){
		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<<"the number "<<x<<" is prime"<<endl;
		cout<<"the number "<<x<<" isn't prime"<<endl;

		cout<<"the number "<<x<<" is prime"<<endl;
		cout<<"the number "<<x<<" isn't prime"<<endl;
		cout << endl;
int GCD_Euclid(int x, int y){
		int r=x%y;

	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();	
Implement the two functions GCD_EuclidRec and GCD_Simple .
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

Last edited by shabbir; 2Oct2010 at 19:43.. Reason: Code blocks
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
Moved to C-C++ forum
jimblumberg's Avatar
Ambitious contributor
It seems to me that you have the "basics of c++" down, your function call all look Ok for a start. Now it's time to add the math.
xpi0t0s's Avatar, Join Date: Aug 2004
anyone on here could probably do it with their eyes closed
Yes, but the problem with this is that you still don't learn anything. You learn programming by programming, not by looking at completed code samples.

The way I write software that I find tricky is to sort out the algorithm on paper first. First I solve a few myself to get the hang of it. Then I solve a few more, working out what steps I'm following. From that I can deduce an algorithm, which I can then translate to code. I use a simplified flowcharting technique: write down a few words describing a simple step, then an arrow pointing to a few more words that describe the next step, and this can develop fairly haphazardly. Arrows can be crossed out and redrawn, new arrows added and drawn in so that they join up two text blocks; the whole thing can look very untidy at the end, then the next step (if necessary) is to tidy up the drawing. Then I dry run it a few times with examples I've previously solved. If I get the same answers then I can translate it to code.

So take it step by step. Do one thing at a time and debug it before you move onto the next. Work out how to do GCD_EuclidRec on paper. What would the GCD_EuclidRec of 100 and 200 be, for example (if those numbers make sense - I just pulled them out of the air)?

A common beginner mistake seems to be to try to write the whole thing in one go - it's not uncommon to see posts here with a description of "thousands of errors - help!" and a 600-line program that's been written and never compiled, and silly errors all over it that could and should have been picked up before getting to 10 lines never mind 600.