Mam taką funkcję liczącą największy wspólny dzielnik za pomocą tych zależności:
\(\displaystyle{ nwd(2n,2m)=2*nwd(n,m)}\)
\(\displaystyle{ nwd(2n,m)=nwd(n,m)}\)- dla nieparzystego \(\displaystyle{ m}\)
Oraz taką do niego funkcję w C++.
Kod: Zaznacz cały
int gcd(int n,int m)
{
int ilenp;
if(!m) return n;
if(n<m) return gcd(m,n);
ilenp = n%2 + m%2;
if(ilenp==2)
return gcd(n-m,m);
if(!ilenp)
return 2*gcd(n/2,m/2);
if(n%2==0)
return gcd(n/2,m);
else
return gcd(n,m/2);
}