--- title: "Crivo de Eratóstenes em Zig — Implementação e Explicação" url: "https://ziglang.com.br/algoritmos/crivo-de-erat%C3%B3stenes-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/" markdown_url: "https://ziglang.com.br/algoritmos/crivo-de-erat%C3%B3stenes-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD" description: "Aprenda o Crivo de Eratóstenes implementado em Zig. Encontre todos os primos até N com código funcional e análise de complexidade." date: "2026-02-21" author: "Zig Brasil" --- # Crivo de Eratóstenes em Zig — Implementação e Explicação Aprenda o Crivo de Eratóstenes implementado em Zig. Encontre todos os primos até N com código funcional e análise de complexidade. # Crivo de Eratóstenes em Zig — Implementação e Explicação O **Crivo de Eratóstenes** é um algoritmo milenar para encontrar todos os números primos até um limite N. É surpreendentemente eficiente: O(n log log n), praticamente linear na prática. ## Como Funciona 1. Cria uma lista de 2 até N, inicialmente todos marcados como primos 2. Para cada número p ainda marcado como primo, marca todos os seus múltiplos como compostos 3. Começa a marcar a partir de p^2 (otimização) 4. Para quando p^2 > N ### Visualização ``` Crivo para N = 30: Inicial: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 p=2: marca 4,6,8,10,12,14,16,18,20,22,24,26,28,30 2 3 . 5 . 7 . 9 . 11 . 13 . 15 . 17 . 19 . 21 . 23 . 25 . 27 . 29 . p=3: marca 9,15,21,27 2 3 . 5 . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . 25 . . . 29 . p=5: marca 25 2 3 . 5 . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . . . . . 29 . 5² = 25 < 30, mas 6² = 36 > 30, então para. Primos: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ``` ## Implementação em Zig ```zig const std = @import("std"); const Allocator = std.mem.Allocator; /// Crivo de Eratóstenes — encontra todos os primos até n. pub fn crivoEratostenes(allocator: Allocator, n: u64) ![]u64 { if (n < 2) return try allocator.alloc(u64, 0); const tamanho: usize = @intCast(n + 1); const eh_primo = try allocator.alloc(bool, tamanho); defer allocator.free(eh_primo); @memset(eh_primo, true); eh_primo[0] = false; eh_primo[1] = false; // Marca compostos var p: usize = 2; while (p * p <= n) : (p += 1) { if (eh_primo[p]) { var multiplo = p * p; while (multiplo <= n) : (multiplo += p) { eh_primo[multiplo] = false; } } } // Coleta primos var primos = std.ArrayList(u64).init(allocator); for (2..tamanho) |i| { if (eh_primo[i]) { try primos.append(@intCast(i)); } } return try primos.toOwnedSlice(); } /// Crivo segmentado para intervalos [lo, hi]. /// Útil quando N é muito grande para caber na memória. pub fn crivoSegmentado( allocator: Allocator, lo: u64, hi: u64, ) ![]u64 { // Primeiro, encontra primos pequenos até sqrt(hi) const limite: u64 = @intFromFloat(@sqrt(@as(f64, @floatFromInt(hi))) + 1); const primos_pequenos = try crivoEratostenes(allocator, limite); defer allocator.free(primos_pequenos); const tamanho: usize = @intCast(hi - lo + 1); const eh_primo = try allocator.alloc(bool, tamanho); defer allocator.free(eh_primo); @memset(eh_primo, true); // Marca compostos no intervalo [lo, hi] for (primos_pequenos) |p| { var inicio = ((lo + p - 1) / p) * p; // primeiro múltiplo de p >= lo if (inicio == p) inicio += p; // não marca o próprio primo while (inicio <= hi) { eh_primo[@intCast(inicio - lo)] = false; inicio += p; } } if (lo <= 1) { if (lo == 0) eh_primo[0] = false; if (lo <= 1) eh_primo[@intCast(1 - lo)] = false; } // Coleta primos no intervalo var primos = std.ArrayList(u64).init(allocator); for (0..tamanho) |i| { if (eh_primo[i]) { try primos.append(lo + @as(u64, @intCast(i))); } } return try primos.toOwnedSlice(); } /// Crivo linear (Euler) — exatamente O(n). pub fn crivoLinear(allocator: Allocator, n: u64) ![]u64 { if (n < 2) return try allocator.alloc(u64, 0); const tamanho: usize = @intCast(n + 1); const menor_primo = try allocator.alloc(u32, tamanho); defer allocator.free(menor_primo); @memset(menor_primo, 0); var primos = std.ArrayList(u64).init(allocator); for (2..tamanho) |i| { if (menor_primo[i] == 0) { menor_primo[i] = @intCast(i); try primos.append(@intCast(i)); } for (primos.items) |p| { if (p > menor_primo[i] or p * @as(u64, @intCast(i)) > n) break; menor_primo[@intCast(p * @as(u64, @intCast(i)))] = @intCast(p); } } return try primos.toOwnedSlice(); } pub fn main() !void { const stdout = std.io.getStdOut().writer(); var gpa = std.heap.GeneralPurposeAllocator(.{}){}; defer _ = gpa.deinit(); const allocator = gpa.allocator(); // Crivo básico const primos = try crivoEratostenes(allocator, 100); defer allocator.free(primos); try stdout.print("Primos até 100 ({d} primos):\n", .{primos.len}); for (primos, 0..) |p, i| { try stdout.print("{d:>3}", .{p}); if ((i + 1) % 10 == 0) try stdout.print("\n", .{}); } try stdout.print("\n", .{}); // Crivo segmentado const seg = try crivoSegmentado(allocator, 100, 150); defer allocator.free(seg); try stdout.print("\nPrimos entre 100 e 150: ", .{}); for (seg) |p| try stdout.print("{d} ", .{p}); try stdout.print("\n", .{}); // Contagem const primos_1m = try crivoEratostenes(allocator, 1_000_000); defer allocator.free(primos_1m); try stdout.print("\nTotal de primos até 1.000.000: {d}\n", .{primos_1m.len}); } ``` ## Análise de Complexidade | Variante | Tempo | Espaço | |----------|-------|--------| | **Crivo básico** | O(n log log n) | O(n) | | **Crivo segmentado** | O(n log log n) | O(sqrt(n)) | | **Crivo linear** | O(n) | O(n) | ## Recursos Relacionados - [Fatoração de Primos](/algoritmos/fatoracao-primos/) — Decompor números em fatores primos - [Euclides (MDC)](/algoritmos/euclides-mdc/) — Máximo divisor comum - [Exponenciação Rápida](/algoritmos/exponenciacao-rapida/) — Potência modular - [BitSet](/estruturas-dados/bitset/) — Otimizar memória do crivo com bits