Criba de primos cronometrada en Mojo

Una criba de Eratóstenes con un cronómetro de nanosegundos alrededor.

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)

Cómo funciona

1. sieve marca cada múltiplo de cada primo, empezando desde su cuadrado.
2. La lista de banderas se transfiere con ^ en vez de copiarse.
3. perf_counter_ns cronometra solo la criba; el conteo pasa después.

Palabras clave y builtins usados aquí

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

El intento, en números

Líneas

35

Caracteres a escribir

746

Tokens

195

Ritmo de tres estrellas

70 tpm

Al ritmo de tres estrellas de 70 tokens por minuto, este intento toma unos 167 segundos.

Escribe este fragmento

Paso 2 de 2 en Bis; paso 22 de 22 en Parámetros y SIMD.

← Anterior