Euclid’s Algorithm for Finding the GCD


The oldest known trivial algorithm known:

int gdc (int x, int y){
    int temp;

    while (y!=0){
        temp=y;
        y=x%y;
        x=temp;
    }

    return x;
}

Check the Wikipedia entry to read more about it.

Leave a Reply

Your email address will not be published. Required fields are marked *