Sieve_of_Eratosthenes.jai

COUNT :: 1_000_000;
arr : [COUNT] bool;
sieve :: () {
    // Computer primes using sieve of Eratosthenes
    for 1..arr.count-1 { arr[it] = true; }
    arr[1] = false;
    for idx: 2..(COUNT / 2) - 1 {
        j := 2 * idx;
        while j < COUNT {
            arr[j] = false;
            j += idx;
        }
    }
}

prime :: (n: u64) -> u64 {
    // find nth prime
    number  : u64 = 1;
    counter : u64 = 1;
    while counter <= n {
        if arr[number] == true then counter += 1;
        number += 1;
    }
    return number-1;
}

primes :: (ps: *[..] u64) {
    for 0..arr.count-1 {
        if arr[it] == true then array_add(ps, cast(u64) it);
    }
}

sep :: "_";
num_fmt :: (n: u64) -> string {
    // It may be a bit ugly, but it works.
    n_str := tprint("%", n);

    buff: String_Builder;
    init_string_builder(*buff);

    did_prefix := false;
    offset := 0;
    if n_str.count % 3 > 0 {
        append(*buff, slice(n_str, 0, n_str.count % 3));
        did_prefix = true;
        offset = n_str.count % 3;
    }

    num_sep := (n_str.count - offset) / 3;
    for 0..num_sep-1 {
        if did_prefix {
            append(*buff, sep);
        } else did_prefix = true;
        i := it * 3 + offset;
        append(*buff, slice(n_str, i, 3));
    }

    return builder_to_string(*buff);
}

main :: () {
    count_fmt := num_fmt(COUNT);
    p_n : u64 = 10;
    p_n_fmt := num_fmt(p_n);

    program_begin := get_time();

    print("Computing sieve (%)\n", count_fmt);
    sieve_begin   := get_time();
    sieve();
    sieve_end     := get_time();

    /*
    print("Finding nth prime (%)\n", p_n_fmt);
    prime_begin   := get_time();
    p := prime(p_n);
    prime_end     := get_time();

    print("%\n", num_fmt(p));
    */

    print("Finding all primes\n");
    primes_begin  := get_time();
    ps : [..] u64;
    primes(*ps);
    primes_end    := get_time();
    print("Primes 1-%: %\n", COUNT, ps.count);

    program_end   := get_time();
    print("\n");
    print("Program : % seconds\n", program_\end - program_\begin);
    print("Sieve   : % seconds\n", sieve_\  end - sieve_\  begin);
    //print("Prime   : % seconds\n", prime_\  end - prime_\  begin);
    print("Primes  : % seconds\n", primes_\ end - primes_\ begin);
}

#import "Basic";
#import "String";