Algoritmo de Euclides – Algoritmos antiguos

Es este artículo de describirá el algortimo de Euclides para encontrar el mayor común divisor entre dos números y su aplicación en varios lenguajes.

El algoritmo de Euclides es un método para encontrar el mayor común divisor entre dos números. El mayor común divisor es el número mayor por el que pueden dividirse ambos números dando como resultado un número entero sin resto.

El algoritmo lleva este nombre ya que su primera descripción escrita se encuentra en el tratado de matemática y geometría los «Elementos de Euclides» escrito en el año 300 a.C., sin embargo se cree que Euclides no fue su creador y el algoritmo ya era conocido por alumnos de la escuela Pitagórica.

Independientemente de el desarrollo del algoritmo en Grecia en India y China se describió el algoritmo para obtener mayor común divisor en diferentes épocas y con diferentes aplicaciones.

En el siglo V el matemático y Aryabhata lo desarrolla como parte su método para resolver para resolver ecuaciones diofánticas de primer orden llamado Algoritmo de Aryabhata.

En China por otra parte su aplicación fue el llamado Teorema chino del resto, una descripción específica de este teorema fue realizada por el astrónomo y matemático Sun Tzu en el siglo V la solución general fue publicada por el matemático Qin Jiushaoen el año 1247.

Algoritmo de Euclides – Algoritmo

Paso 1

Llamar A al B mayor y B al menor de los números

A=162078
B=960

Paso 2

Obtener resto de dividir A y B

162078/960=138
Resto=798

Paso 3

Asignar el valor más pequeño a A

A=960

Paso 4

Asignar el resto a B

B=798

Paso 5

Mientras que el resto sea diferente de 0 hacer Pasos 2, 3 y 5

960/798=1
Resto=162
A=798
B=162

798/162=4
Resto=150
A=162
B=150

162/150=12
Resto=6
A=150
B=6

150/6=2
Resto=0
A=6
B=0

Al finalizar el algoritmo el valor de A será el mayor común divisor

MCP=6

• Pseudocódigo con Pseint
• Algoritmo para PHP
• Algorimto para C
• Algoritmo para Python

Pseudocódigo para PSeint

Proceso Euclides
//Algoritmo de Euclides
	a=162078;
	b=960;
	temporal=0;
	//1- Hacer que el valor a sea el mayor
	Si(a<b)
		temporal=a;
		a=b;
		b=temporal;
	FinSi
	//2- Si el resto es igual a 0 termina el algoritmo
	Mientras b!=0 Hacer
		//3-Calcular el resto de dividir a y b
		resto=a%b;
		Escribir "Division " a/b;
		Escribir "Resto " a%b;
		//4-Asignar el valor más pequeño a a
		a=b;
		//5-Asignar el resto a b
		b=resto;
		Escribir a;
	FinMientras
	
Escribir "Resultado Final: " a; 

FinProceso

Código para PHP

<?php
    //Algoritmo de Euclides
    $a=162078;
    $b=960;
    $temporal=0;
    //1- Hacer que el valor a sea el mayor 
	if($a<$b)
	{	
		$temporal=$a;
		$a=$b;
		$b=$temporal;
	}
	//2- Si el resto es igual a 0 termina el algoritmo 
	while($b!=0)
	{
		//3-Calcular el resto de dividir a y b 
		$resto=$a%$b;
		//4-Asignar el valor más pequeño a a 
		$a=$b;
		//5-Asignar el resto a b 
		$b=$resto;
		echo "$a <br/>";
	}
	echo "Resultado Final: $a";
	

Código para C

#include<stdio.h>
int main(int argc, char** argv){
       //Algoritmo de Euclides
	int a = 162078;
	int b = 960;
	int temporal=0;
	int resto=0;

	//1- Hacer que el valor a sea el mayor 
	if(a<b)	{	
		temporal=a;
		a=b;
		b=temporal;
	}
	
	//2- Si el resto es igual a 0 termina el algoritmo 
	while(b!=0){
		//3-Calcular el resto de dividir a y b 
		resto=a%b;
		//4-Asignar el valor más pequeño a a 
		a=b;
		//5-Asignar el resto a b 
		b=resto;
		printf("%d\n",a);
	}
	printf("Resultado Final: %d\n",a);
	return 0;

}

Código para Python

#Algoritmo de Euclides
a=162078
b=960
temporal=0
#1- Hacer que el valor a sea el mayor 
if a<b:
	temporal=a
	a=b
	b=temporal
#2- Si el resto es igual a 0 termina el algoritmo 
while b!=0:
	#3-Calcular el resto de dividir a y b 
	resto=a%b
	#4-Asignar el valor más pequeño a a 
	a=b
	#5-Asignar el resto a b 
	b=resto
	print(a)
print("Resultado Final:"+str(a))

Este sencillo algoritmo ha sido ampliamente utilizado en diferentes ramas de la matemática siendo aplicado en la criptografía moderna.