Prime number generation with Sieve of Eratosthenes algorithm

From Wikipedia:

In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime. This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime. Once all the multiples of each discovered prime have been marked as composites, the remaining unmarked numbers are primes.

This is my first code snippet in Zig, implementing the Sieve of Eratosthenes algorithm. As the first step, the standard library is associated with the constant std. The algorithm is implemented inside a function called sieve. That receives the maximum limit number. An array for boolean values is created.

const std = @import("std");

fn sieve(n: u32) !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    var alloc = gpa.allocator();
    var v = try alloc.alloc(bool, n + 1);
    defer alloc.free(v);

Every element in the array represents a flag to indicate whether its index is a primer number of not. At the beginning, all flags in the array are set to true, except postions 0 and 1, given that these last ones are not prime numbers.

    var i: u32 = 0;
    while (i <= n) : (i += 1)
        v[i] = true;

    v[0] = false;
    v[1] = false;

One property of natural numbers is that their factors are less or equal to their square root ($f \leq \sqrt{n}$). Therefore, to identify non prime numbers, we just need to loop up to the square root of the maximum number required. For example, if the maximum number is 120, we just need to loop until 10. In every step, all multiples of the value being evaluated, except itself, are set as false. At the end, flags which value remain true in the array are the ones which indices represent prime numbers.

    i = 2;
    while (i * i <= n) : (i += 1)
        if (v[i]) {
            var j = i * i;
            while (j <= n) : (j += i)
                v[j] = false;
        };

In this example, the last action in the function is to print the set of prime numbers identified.

    i = 0;
    while (i <= n) : (i += 1)
        if (v[i]) std.debug.print("{}\n", .{i});
}

Here is the complete listing:

/// Sieve of Eratosthenes Algorithm
/// Finding prime numbers less or equal than n
const std = @import("std");

/// Function implementing
/// Sieve of Eratosthenes Algorithm
fn sieve(n: u32) !void {
    // Allocating memory for prime flags array
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    var alloc = gpa.allocator();
    var v = try alloc.alloc(bool, n + 1);
    defer alloc.free(v);

    // Initilizating prime flags array
    // At the beginnig, all flags are set to true
    var i: u32 = 0;
    while (i <= n) : (i += 1)
        v[i] = true;

    // Trivial cases
    v[0] = false;
    v[1] = false;

    // Identifying false cases
    i = 2;
    while (i * i <= n) : (i += 1)
        if (v[i]) {
            var j = i * i;
            while (j <= n) : (j += i)
                v[j] = false;
        };

    // Printing the list of prime numbers
    i = 0;
    while (i <= n) : (i += 1)
        if (v[i]) std.debug.print("{}\n", .{i});
}

pub fn main() !void {
    try sieve(1000);
}

Date: 2023-12-27
Updated: 2023-12-28