Greatest common factor using euclid's algorithm

[frantheman27]

My task is to write a profram that finds the gcf of 2 integers. Im supposed to use a Euclidian algorithm and it really confuses me. Im supposed to write the gcf function and then implement it in my int main.

Heres what it says.

Implement the Euclidean Algorithm for finding the greatest common factor of two given positive integers. If the given pair is (m, n), the algorithm will transform it into the pair (d, 0), where d is the GCF of the pair (m, n). The algorithm works like this:


1. Divide m by n and get the remainder, r
2. Store n into m, and r into n
3. If r is 0, the GCF is m, if not repeat steps 1-3


Ive got this code and whenever i input 2 integers it outputs nothing

  #include <iostream>
#include <string>

using namespace std;

int gcf( int m, int n);
// returns gcf of m and n

int main() {
    int m;
    int n;
    cout << " Type 2 integers:";
    cin >> m >> n;
    cout << gcf(m, n);
return 0;
}

int gcf( int m, int n) {
    int r = m%n;
    if(r == 0) {
        int r = m;
    }
    else {
        do{
           n = r;
           m = n;
    }while(r != 0);
    }
return r;
}

[helios]

Line 21: You're not changing the value of r from line 19, you're creating a new, different variable named 'r' and settings it to m. Remove the int part.
Lines 25 and 26: You're not doing things in the order the algorithm gives.

Store n into m, and r into n

Lines 24-27: Your loop doesn't do everything the algorithm states.

If r is 0, the GCF is m, if not repeat steps 1-3

Your loop only performs steps 2 and 3.

[frantheman27]

So if it states store n into m would i put m = n;or would it be the other way around? And sm i right to use a loop for steps 1-3?

[koopey]

if it states store n into m would i put m = n;or would it be the other way around?

it should strictly be "m=n". and the loop doesn't seem to be right. try using a do-while loop from the start of gcf function.

[Arslan7041]

Here is a an amazingly clear video that explains Euclids algorithm: https://www.youtube.com/watch?v=7HCd074v8g8

This is the recursive version of it (which, in my opinion, is a lot more intuitive).