---
title: "Algoritmo de Euclides (MDC) em Zig — Implementação e Explicação"
url: "https://ziglang.com.br/algoritmos/algoritmo-de-euclides-mdc-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/"
markdown_url: "https://ziglang.com.br/algoritmos/algoritmo-de-euclides-mdc-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD"
description: "Aprenda o algoritmo de Euclides para MDC implementado em Zig. Versões iterativa, recursiva, estendida e MMC com código funcional."
date: "2026-02-21"
author: "Zig Brasil"
---

# Algoritmo de Euclides (MDC) em Zig — Implementação e Explicação

Aprenda o algoritmo de Euclides para MDC implementado em Zig. Versões iterativa, recursiva, estendida e MMC com código funcional.


# Algoritmo de Euclides (MDC) em Zig — Implementação e Explicação

O **Algoritmo de Euclides** calcula o **Máximo Divisor Comum (MDC)** de dois números. É um dos algoritmos mais antigos conhecidos (circa 300 a.C.) e ainda é usado extensivamente em criptografia, frações e teoria dos números.

## Como Funciona

O princípio é simples: MDC(a, b) = MDC(b, a mod b), e MDC(a, 0) = a.

### Visualização

```
MDC(252, 105):
  252 = 2 × 105 + 42    → MDC(252, 105) = MDC(105, 42)
  105 = 2 × 42 + 21     → MDC(105, 42)  = MDC(42, 21)
   42 = 2 × 21 + 0      → MDC(42, 21)   = MDC(21, 0)

  MDC(252, 105) = 21

Euclides Estendido — encontra x, y tal que ax + by = MDC(a, b):
  MDC(252, 105) = 21
  21 = 105 - 2×42
  42 = 252 - 2×105
  21 = 105 - 2×(252 - 2×105) = 5×105 - 2×252
  Então: 252×(-2) + 105×5 = 21 ✓
```

## Implementação em Zig

```zig
const std = @import("std");

/// MDC iterativo — O(log(min(a,b))).
pub fn mdc(a_param: u64, b_param: u64) u64 {
    var a = a_param;
    var b = b_param;
    while (b != 0) {
        const temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

/// MDC recursivo.
pub fn mdcRecursivo(a: u64, b: u64) u64 {
    if (b == 0) return a;
    return mdcRecursivo(b, a % b);
}

/// Mínimo Múltiplo Comum usando MDC.
pub fn mmc(a: u64, b: u64) u64 {
    if (a == 0 or b == 0) return 0;
    return (a / mdc(a, b)) * b; // evita overflow
}

/// Euclides Estendido — encontra x, y tal que ax + by = MDC(a, b).
pub fn mdcEstendido(a: i64, b: i64) struct { mdc_val: i64, x: i64, y: i64 } {
    if (a == 0) {
        return .{ .mdc_val = b, .x = 0, .y = 1 };
    }

    const resultado = mdcEstendido(@rem(b, a), a);
    return .{
        .mdc_val = resultado.mdc_val,
        .x = resultado.y - @divTrunc(b, a) * resultado.x,
        .y = resultado.x,
    };
}

/// Inverso modular usando Euclides Estendido.
/// Retorna x tal que (a * x) mod m = 1, ou null se não existir.
pub fn inversoModular(a: i64, m: i64) ?i64 {
    const resultado = mdcEstendido(a, m);
    if (resultado.mdc_val != 1) return null;
    return @mod(resultado.x, m);
}

/// MDC de múltiplos números.
pub fn mdcMultiplo(numeros: []const u64) u64 {
    if (numeros.len == 0) return 0;
    var resultado = numeros[0];
    for (numeros[1..]) |n| {
        resultado = mdc(resultado, n);
        if (resultado == 1) return 1;
    }
    return resultado;
}

/// MMC de múltiplos números.
pub fn mmcMultiplo(numeros: []const u64) u64 {
    if (numeros.len == 0) return 0;
    var resultado = numeros[0];
    for (numeros[1..]) |n| {
        resultado = mmc(resultado, n);
    }
    return resultado;
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();

    // MDC simples
    const pares = [_][2]u64{
        .{ 252, 105 },
        .{ 48, 18 },
        .{ 100, 75 },
        .{ 17, 13 },
    };

    try stdout.print("=== MDC e MMC ===\n", .{});
    for (pares) |par| {
        try stdout.print("MDC({d}, {d}) = {d}, MMC = {d}\n", .{
            par[0], par[1], mdc(par[0], par[1]), mmc(par[0], par[1]),
        });
    }

    // Euclides Estendido
    try stdout.print("\n=== Euclides Estendido ===\n", .{});
    const ext = mdcEstendido(252, 105);
    try stdout.print("252x + 105y = MDC → x={d}, y={d}, MDC={d}\n", .{ ext.x, ext.y, ext.mdc_val });
    try stdout.print("Verificação: 252×({d}) + 105×({d}) = {d}\n", .{
        ext.x, ext.y, 252 * ext.x + 105 * ext.y,
    });

    // Inverso modular
    try stdout.print("\n=== Inverso Modular ===\n", .{});
    if (inversoModular(3, 7)) |inv| {
        try stdout.print("Inverso de 3 mod 7 = {d} (3×{d} mod 7 = {d})\n", .{
            inv, inv, @mod(3 * inv, 7),
        });
    }

    // MDC de múltiplos números
    const nums = [_]u64{ 12, 18, 24, 36 };
    try stdout.print("\nMDC(12, 18, 24, 36) = {d}\n", .{mdcMultiplo(&nums)});
    try stdout.print("MMC(12, 18, 24, 36) = {d}\n", .{mmcMultiplo(&nums)});
}
```

## Análise de Complexidade

| Operação | Tempo | Espaço |
|----------|-------|--------|
| **MDC (iterativo)** | O(log(min(a,b))) | O(1) |
| **MDC (recursivo)** | O(log(min(a,b))) | O(log(min(a,b))) |
| **MDC Estendido** | O(log(min(a,b))) | O(log(min(a,b))) |
| **MMC** | O(log(min(a,b))) | O(1) |

## Aplicações

- **Simplificar frações**: dividir numerador e denominador pelo MDC
- **Criptografia RSA**: encontrar inverso modular para chaves
- **Problemas de divisibilidade**: MDC e MMC em competições
- **Sincronização**: MMC para encontrar períodos coincidentes

## Recursos Relacionados

- [Crivo de Eratóstenes](/algoritmos/crivo-eratostenes/) — Encontrar números primos
- [Exponenciação Rápida](/algoritmos/exponenciacao-rapida/) — Potência modular eficiente
- [Fatoração de Primos](/algoritmos/fatoracao-primos/) — Decompor em fatores primos
- [Fibonacci por Matriz](/algoritmos/fibonacci-matrix/) — Usa aritmética modular