Download

← Examples

primes

The sieve of Eratosthenes, up to 100.

examples/primes in the repository.

// Sieve of Eratosthenes: print all primes ≤ N.
//
// Allocates a `bool` array of length N+1 where `composite[i]` flips to true
// once any multiple of `i` lands on it. The remaining `false` slots are the
// primes. Classic O(N log log N) ; far more efficient than trial-division
// for any non-trivial bound.

module "main"

import "std/io"

N :: 100

main :: fn() -> i32 {
    composite: bool[]: []
    for i in 0..=N {
        composite.push(false)
    }

    p := 2
    for p * p <= N {
        if !composite[p] {
            // Mark every multiple of p starting at p² (smaller multiples
            // were already marked when we walked p's smaller factors).
            k := p * p
            for k <= N {
                composite[k] = true
                k = k + p
            }
        }
        p = p + 1
    }

    println("Primes up to ${N}:")
    first := true
    for n in 2..=N {
        if !composite[n] {
            if first {
                print("${n}")
                first = false
            } else {
                print(", ${n}")
            }
        }
    }
    println("")
    return 0
}