Greatest common divisor

[AndreasTm13]

From the keyboard are introduced the natural number n and k(2<=k<=n).I have to display all of the pairs of natural numbers < than n,of which greatest common divisor is k.
Example: n=10; k=2;
There will be displayed: 2 4;2 6;2 8;2 10;4 6;4 10;6 10;8 10;(I hope I haven't got something wrong in the example)

    int n,k,a,b,x;
    cout<<"n=";cin>>n;
    cout<<"k=";cin>>k;
    if(2<=k && k<=n)
    {
        b=n-1;
        x=b;
        for(a=1;a<n;a++)
        {
            while(a!=x)
            {
                if(a>x)
                    a=a-x;
                else x=x-a;
            }
            if(a==k||b==k)
            {
                cout<<a<<endl;
                cout<<b<<endl;
            }
        }
    }

The code does not display nothing.

[Handy Andy]

Hello AndreasTm13,

The one problem I see is that the while loop at line 10 creates an endless loop for line 8. Have not figured out the rest yet, but I think the while loop is not working right and the if statement at line 16 always ends up false and bypassed.

Hope that hlps,

Andy

Edit line 13 changes the value of "a" which makes a mess out of the for loop at line 8 making it an endless loop.

[jonnin]

I don't see modulus in there.. I think you want this classic algorithm (its thousands of years old, interestingly) (:= is assignment in this pseudocode)

gcd(a, b)
while b ≠ 0
t := b;
b := a mod b;
a := t;
return a;

[Handy Andy]

Hello AndreasTm13,

I agree with jonnin the use of the "%" (modulo) operator is needed.

Doing a Google search on "greatest common divisor" lead me to this web page
http://www.mathportal.org/calculators/numbers-calculators/gcd-lcm-calculator.php
which gave me a better understanding of GCD which your program is not doing.

Hope that helps,

Andy