Programación en lenguaje C, utilizando el método de división euclidiana para encontrar divisores comunes

El algoritmo euclidiano, también conocido como algoritmo euclidiano, es un algoritmo para encontrar el máximo común divisor de dos números enteros positivos.

El principio es el siguiente:

Supongamos que los dos números son a y b (b

El primer paso: Sea c=gcd(a,b), luego sea a=mc, b=nc

El segundo paso: Según la premisa, sabemos que r =a-kb= mc-knc=(m-kn)c

Paso 3: Según el resultado del paso 2, sabemos que c también es factor de r

Paso 4: Se puede concluir que m-kn y n De lo contrario, podemos asumir que m-kn=xd, n=yd (d>1), entonces m=kn+xd=kyd+xd=(ky+x) d, entonces a=mc=(ky+x)dc, b=nc=ycd, por lo que el máximo común divisor de a y b se convierte en cd en lugar de c, lo cual es contradictorio con la conclusión anterior

Así se puede ver que mcd(b,r)=c, y luego mcd(a,b) =mcd(b,r).

Certificado completado.

Los pasos anteriores se basan en r!=0 al principio. Es decir, myn también son primos entre sí.

Según sus reglas, el lenguaje C se implementa de la siguiente manera: int?GCD(int?a,int?b)

{return?b==0? a:MCD(b,a%b);}