Calculadora de Máximo Común Divisor de dos números. Útil para criptografía.

Dos números son coprimos o primos entre sí cuando no tienen divisores en común (excepto 1 y -1). Por tanto, la manera de saber si dos números son coprimos es ver sus divisores. Si hay algún divisor en común entre los dos números además del 1, los números no son coprimos y si no existen, sí son coprimos.

También sabemos que el máximo común divisor de dos números coprimos es siempre 1. Por lo que también tenemos otra manera de saber cuando dos números son coprimos mirando su MCD.

MCD (A, B) = 1 ==> ENTONCES A Y B SON COPRIMOS

#!/usr/bin/python
# -*- coding: utf-8 -*-
#
# CALCULADORA M.C.D DE DOS NUMEROS. UTIL PARA CRIPTOGRAFIA, CIFRADO RSA. 
# TRABAJAMOS CON DOS FUNCIONES
print
print "Calculadora de numeros coprimos o primos relativos entre si"
print 

# DEFINIMOS LA PRIMERA FUNCION

x = input("Introduce el primer numero: ")   # INTRODUCIMOS LOS DOS NUMEROS A COMPROBAR
y = input("Introduce el segundo numero: ")

def mcd(a, b):
    if b == 0: 
        return a
    else:
        return mcd(b, a%b) 

#print mcd(x, y) 

print
print "El Maximo Comun Divisor de ", x, "y ", y," es: ", mcd(x, y) 
print

if mcd(x, y) == 1: 
    print "Los numeros SON coprimos o primos relativos entre si"
else:
    print "Los numeros NO SON coprimos entre si"
print 

# SEGUNDA FUNCION 

def mcd(a, b):
    resto = 0
    while(b > 0):
        resto = b
        b = a % b
        a = resto 
    return a

num1 = int(input("Introduce el primer numero: ")) 
num2 = int(input("Introduce el segundo numero: ")) 

print 
print "El Maximo Comun Divisor de ", num1, " y " , num2, " es: ", mcd(num1, num2) 
print
if mcd(num1 ,num2) == 1: 
    print "Los números SON coprimos o primos relativos entre si"
else: 
    print "Los números NO SON coprimos entre si" 
print

Presentamos un script con dos funciones que hayan el Máximo Común Divisor de dos números. Nos pedirá que ingresemos dos números.

Si por ejemplo, ingresamos los números 1 y 7 nos dirá que SON COPRIMOS o PRIMOS RELATIVOS ENTRE SÍ, ya que 1 y 7 solo son divisibles por 1.

Si ingresamos los números 9 y 27 nos dirá que los números NO SON COPRIMOS ya que 9 y 27 son divisibles también por el número 9.

Si ingresásemos los números 3 y 15 nos diría que NO SON COPRIMOS ya que ambos se pueden dividir por 3.

Compártelo:

Relacionado

Publicado por anjnicoantonio