Timed prime sieve in Mojo

A sieve of Eratosthenes with a nanosecond timer wrapped around it.

from std.time import perf_counter_ns


def sieve(limit: Int) -> List[Bool]:
    var is_prime = List[Bool](capacity=limit + 1)
    for _ in range(limit + 1):
        is_prime.append(True)
    is_prime[0] = False
    is_prime[1] = False
    var step = 2
    while step * step <= limit:
        if is_prime[step]:
            var multiple = step * step
            while multiple <= limit:
                is_prime[multiple] = False
                multiple += step
        step += 1
    return is_prime^


def main():
    var limit = 200000
    var start = perf_counter_ns()
    var flags = sieve(limit)
    var elapsed = perf_counter_ns() - start
    var count = 0
    var largest = 0
    for n in range(limit + 1):
        if flags[n]:
            count += 1
            largest = n
    print("limit:", limit)
    print("primes found:", count)
    print("largest prime:", largest)
    print("sieve microseconds:", elapsed // 1000)

How it works

1. sieve marks every multiple of each prime, starting from its square.
2. The flag list is transferred out with ^ instead of being copied.
3. perf_counter_ns times the sieve alone; the counting happens afterward.

Keywords and builtins used here

• Int
• List
• def
• for
• if
• main
• print
• range
• return
• sieve
• var
• while

The run, in numbers

Lines

35

Characters to type

746

Tokens

195

Three-star pace

70 tpm

At the three-star pace of 70 tokens a minute, this run takes about 167 seconds.

Type this snippet

Step 2 of 2 in Encore, step 22 of 22 in Parameters & SIMD.

← Previous