Fatorar 360:
  360 ÷ 2 = 180    → 2
  180 ÷ 2 = 90     → 2
  90 ÷ 2 = 45      → 2
  45 ÷ 3 = 15      → 3
  15 ÷ 3 = 5       → 3
  5 ÷ 5 = 1        → 5

  360 = 2³ × 3² × 5¹

Fatorar 1000000007:
  Não divisível por 2, 3, 5, ..., até sqrt(10^9) ≈ 31623
  → 1000000007 é primo!

const std = @import("std");
const Allocator = std.mem.Allocator;

const Fator = struct {
    primo: u64,
    expoente: u32,
};

/// Fatoração por trial division — O(sqrt(n)).
pub fn fatorar(allocator: Allocator, n_param: u64) ![]Fator {
    var fatores = std.ArrayList(Fator).init(allocator);
    var n = n_param;

    if (n <= 1) return try fatores.toOwnedSlice();

    // Divide por 2
    if (n % 2 == 0) {
        var exp: u32 = 0;
        while (n % 2 == 0) {
            n /= 2;
            exp += 1;
        }
        try fatores.append(.{ .primo = 2, .expoente = exp });
    }

    // Divide por ímpares de 3 até sqrt(n)
    var d: u64 = 3;
    while (d * d <= n) : (d += 2) {
        if (n % d == 0) {
            var exp: u32 = 0;
            while (n % d == 0) {
                n /= d;
                exp += 1;
            }
            try fatores.append(.{ .primo = d, .expoente = exp });
        }
    }

    // Se n > 1, então n é primo
    if (n > 1) {
        try fatores.append(.{ .primo = n, .expoente = 1 });
    }

    return try fatores.toOwnedSlice();
}

/// Conta o número total de divisores a partir da fatoração.
pub fn contarDivisores(fatores: []const Fator) u64 {
    var total: u64 = 1;
    for (fatores) |f| {
        total *= @as(u64, f.expoente) + 1;
    }
    return total;
}

/// Soma de todos os divisores a partir da fatoração.
pub fn somaDivisores(fatores: []const Fator) u64 {
    var total: u64 = 1;
    for (fatores) |f| {
        // (p^(e+1) - 1) / (p - 1)
        var soma_fator: u64 = 0;
        var potencia: u64 = 1;
        for (0..f.expoente + 1) |_| {
            soma_fator += potencia;
            potencia *= f.primo;
        }
        total *= soma_fator;
    }
    return total;
}

/// Função totiente de Euler (phi) a partir da fatoração.
pub fn eulerTotiente(fatores: []const Fator) u64 {
    var resultado: u64 = 1;
    for (fatores) |f| {
        // phi(p^e) = p^(e-1) * (p - 1)
        var potencia: u64 = 1;
        for (0..f.expoente - 1) |_| {
            potencia *= f.primo;
        }
        resultado *= potencia * (f.primo - 1);
    }
    return resultado;
}

/// Fatoração com crivo pré-computado — O(log n) por consulta.
pub const FatoradorRapido = struct {
    menor_primo: []u32,
    allocator: Allocator,

    pub fn init(allocator: Allocator, limite: u32) !FatoradorRapido {
        const menor_primo = try allocator.alloc(u32, @intCast(limite + 1));
        for (0..limite + 1) |i| {
            menor_primo[i] = @intCast(i);
        }

        var i: u32 = 2;
        while (@as(u64, i) * i <= limite) : (i += 1) {
            if (menor_primo[i] == i) { // i é primo
                var j = i * i;
                while (j <= limite) : (j += i) {
                    if (menor_primo[j] == j) {
                        menor_primo[j] = i;
                    }
                }
            }
        }

        return .{ .menor_primo = menor_primo, .allocator = allocator };
    }

    pub fn deinit(self: *FatoradorRapido) void {
        self.allocator.free(self.menor_primo);
    }

    /// Fatora n em O(log n) usando o crivo pré-computado.
    pub fn fatorarRapido(self: *const FatoradorRapido, allocator: Allocator, n_param: u32) ![]Fator {
        var fatores = std.ArrayList(Fator).init(allocator);
        var n = n_param;

        while (n > 1) {
            const p = self.menor_primo[n];
            var exp: u32 = 0;
            while (n > 1 and self.menor_primo[n] == p) {
                n /= p;
                exp += 1;
            }
            try fatores.append(.{ .primo = p, .expoente = exp });
        }

        return try fatores.toOwnedSlice();
    }
};

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // Fatoração básica
    const numeros = [_]u64{ 360, 1024, 997, 123456789, 1000000007 };

    try stdout.print("=== Fatoração em Primos ===\n", .{});
    for (numeros) |n| {
        const fatores = try fatorar(allocator, n);
        defer allocator.free(fatores);

        try stdout.print("{d} = ", .{n});
        for (fatores, 0..) |f, i| {
            if (i > 0) try stdout.print(" x ", .{});
            if (f.expoente == 1) {
                try stdout.print("{d}", .{f.primo});
            } else {
                try stdout.print("{d}^{d}", .{ f.primo, f.expoente });
            }
        }
        try stdout.print("\n", .{});

        // Informações extras
        try stdout.print("  Divisores: {d}, Soma: {d}, Phi: {d}\n", .{
            contarDivisores(fatores),
            somaDivisores(fatores),
            eulerTotiente(fatores),
        });
    }

    // Fatoração rápida com crivo
    try stdout.print("\n=== Fatoração Rápida (Crivo) ===\n", .{});
    var fatorador = try FatoradorRapido.init(allocator, 1_000_000);
    defer fatorador.deinit();

    const fat = try fatorador.fatorarRapido(allocator, 360);
    defer allocator.free(fat);
    try stdout.print("360 (rápido) = ", .{});
    for (fat, 0..) |f, i| {
        if (i > 0) try stdout.print(" x ", .{});
        try stdout.print("{d}^{d}", .{ f.primo, f.expoente });
    }
    try stdout.print("\n", .{});
}