Algoritmo de Euclides – Algoritmos antiguos

Publicado por Andrea Navarro en

Euclides -Algoritmo de Euclides

Euclides

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.

Aryabhata

Aryabhata

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 Jiushao en 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

Mientras que el resto sea diferente de 0 hacer Paso 3, 4 y 5

Paso 3

Obtener resto de dividir A y B

162078/960=138
Resto=798

Paso 4

Asignar el valor más pequeño a A

A=960

Paso 5

Asignar el resto a B

B=798

Segunda iteración

Obtener resto de dividir A y B

960/798=1
Resto=162

Asignar el valor más pequeño a A

A=798

Asignar el resto a B

B=162

Tercera iteración

Obtener resto de dividir A y B

798/162=4
Resto=150

Asignar el valor más pequeño a A

A=162

Asignar el resto a B

B=150

Cuarta iteración

Obtener resto de dividir A y B

162/150=12
Resto=6

Asignar el valor más pequeño a A

A=150

Asignar el resto a B

B=6

Quinta iteración

Obtener resto de dividir A y B

150/6=2
Resto=0

Asignar el valor más pequeño a A

A=6

Asignar el resto a B

B=0

Fin del algoritmo

MCP=6

Pseudocodigo 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;

}

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


Andrea Navarro

- Ingeniera en Informática - Docente universitaria - Investigadora