Skip to content
ExamplesEspañolWorkspace →

GCD and LCM

Computes the greatest common divisor and the least common multiple.

Level
Intermediate
Topic:
Math
Concepts:
Input & output
Functions
Mientras
Math
Open in Codoritmo

Run, change and debug this example in your browser.

What you'll learn

The MCD Funcion runs Euclid's algorithm with Mientras and MOD. The LCM comes from the GCD, using Trunc to keep a whole number.

Code

gcd-lcm.psc · 25 lines
Funcion resultado <- MCD(a, b)    Definir resultado, resto Como Entero    // Algoritmo de Euclides    Mientras b <> 0 Hacer        resto <- a MOD b        a <- b        b <- resto    FinMientras    resultado <- aFinFuncionAlgoritmo MCDyMCM    Definir a, b, divisor Como Entero    Escribir "Primer número:"    Leer a    Escribir "Segundo número:"    Leer b    Si a <= 0 O b <= 0 Entonces        Escribir "Usa números enteros positivos."    SiNo        divisor <- MCD(a, b)        Escribir "MCD(", a, ", ", b, ") = ", divisor        Escribir "MCM(", a, ", ", b, ") = ", Trunc(a * b / divisor)    FinSiFinAlgoritmo

Flowchart

Each block in the flowchart matches one instruction in the code.

Algoritmo MCDyMCM
Algoritmo MCDyMCMSíNoAlgoritmo MCDyMCMAlgoritmo MCDyMCMDefinir a, b, divisor Como EnteroDefinir a, b, divisor ComoEnteroEscribir "Primer número:"Escribir "Primer número:"Leer aLeer aEscribir "Segundo número:"Escribir "Segundo número:"Leer bLeer bSi a <= 0 O b <= 0 Entoncesa <= 0 O b <= 0Escribir "Usa números enteros positivos."Escribir "Usa números enterospositivos."divisor <- MCD(a, b)divisor <- MCD(a, b)Escribir "MCD(", a, ", ", b, ") = ", divisorEscribir "MCD(", a, ", ", b,") = ", divisorEscribir "MCM(", a, ", ", b, ") = ", Trunc(a * b / divisor)Escribir "MCM(", a, ", ", b,") = ", Trunc(a * b / divisor)FinAlgoritmoFinAlgoritmo
Funcion MCD
Funcion MCDSíNoFuncion resultado <- MCD(a, b)Funcion resultado <- MCD(a, b)Definir resultado, resto Como EnteroDefinir resultado, resto ComoEnteroMientras b <> 0 Hacerb <> 0resto <- a MOD bresto <- a MOD ba <- ba <- bb <- restob <- restoresultado <- aresultado <- aFinFuncion (devuelve resultado)FinFuncion (devuelve resultado)

Sample run

This is what the program shows when it runs. The answers typed by the user are highlighted.

Primer número:User answer: 12Segundo número:User answer: 18MCD(12, 18) = 6MCM(12, 18) = 36

Complexity

How much work and memory it needs as the amount of data (n) grows.

Complexity
CaseCost
BestO(1)
AverageO(log n)
WorstO(log n)
MemoryO(1)

Challenge

Ask for three numbers and compute the GCD of all three.

Show hint

The GCD of three numbers is MCD(MCD(a, b), c).

Open in Codoritmo

Related examples