# Simple Program to find GCF

1. Feb 25, 2009

### moo5003

1. The problem statement, all variables and given/known data

I'm reading through a text on cryptography independently and I'm learning c++ as I go to write some of the things in a program. For some reason I cannot get this to work and I was wondering if anyone could tell me what I'm doing wrong.

The program is supposed to find the GCF of two numbers using Euclids algorythm.

3. The attempt at a solution

#include <iostream>
using namespace std;

int main()
{
cout << "Please input a number for a: ";
int a;
cin >> a;
cout << "Please input a number for b: ";
int b;
cin >> b;
cout << "You have entered: " << a << "," << b << "\n";
int q;
int r;
q = a % b;
r = a - (q*b);
int n = 1;
int x = a;
int y = b;

while (r >= 1)
{
a = b;
b = r;
q = a % b;
r = a - (q*b);
cout << "Step " << n << " - a=" << a << ", b=" << b << ", r=" << r << "\n";
n = n + 1;
}

cout << "The GCD(" << x << "," << y << ") = " << b;

return 0;
}

Nevermind after posting it on here I just noticed q = a mod b... which would be r :/.