Calcular el máximo común divisor

David Vega

Programa que calcula el máximo común divisor de dos números (he visto que otros ya lo habían hecho, pero el único de ellos que no estaba en C me pareció demasiado largo).

El cálculo del m.c.d. puede tener aplicaciones en una clave RSA, por ejemplo.


/*Este programa halla el máximo común divisor de dos números (D,d) introducidos
por el usuario. Para ello, utiliza el algoritmo de Euclides, que se puede resumir en:
sabiendo que si llamamos "D" al dividendo, "d" al divisor, "c" al cociente y "r"
al resto se cumple D=d·c+r, si "D" tiene un divisor "a", y si "d" también lo tiene,
entonces "r" ha de tenerlo también.
El máximo común divisor de "D" y "d" es "a" (y es el mismo que el de "d" y "r").*/

// Programa creado por David Vega.

#include <iostream>
using namespace std;

int main()
{
 int D,d,r,var;

 do { cout << "Dame un par de numeros enteros positivos: " << endl;
 cin >> D >> d;
 }
 while(d<=0 || D<=0);
 if(d>D) // Si la segunda variable es mayor que la primera, las intercambiamos
 {
 var=d; // Para ello utilizamos una variable temporal de cambio
 d=D;
 D=var;
 }
 while(D%d !=0) // Usamos un bucle que hace el algoritmo de Euclides.
 {
 r=D%d;
 D=d;
 d=r;
 }
 cout << endl << "El m.c.d. es " << d << ".";
 return 0;
}

Esta entrada fue publicada en Informática e Internet. Guarda el enlace permanente.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s