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

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});
}