MojoでProject Euler 7

https://projecteuler.net/problem=7

配列にはいろいろな種類があるようです。ここでは2種類を使います。
Pointerはallocateして最後にfreeするというCで領域確保するのと同じものです。恐ろしいですね。
DynamicVectorはpush_backして要素を追加できるので、Pythonのリストと同じように書けます。
コードは後回しで速度測定すると、

$ time python e007.py 10000001
179424691

real    0m36.194s
user    0m35.917s
sys     0m0.230s

$ time pypy3 e007.py 10000001
179424691

real    0m5.887s
user    0m5.268s
sys     0m0.601s

$ time mojo e007.mojo 10000001
179424691

real    0m0.868s
user    0m0.831s
sys     0m0.051s

$ mojo build e007.mojo -o e007_mojo
$ time ./e007_mojo 10000001
179424691

real    0m0.808s
user    0m0.790s
sys     0m0.011s

$ g++ -O3 e007.cpp -o e007_cpp
$ time ./e007_cpp 10000001
179424691

real    0m0.657s
user    0m0.624s
sys     0m0.030s

$ rustc -C opt-level=3 e007.rs -o e007_rust
$ time ./e007_rust 10000001
179424691

real    0m0.847s
user    0m0.835s
sys     0m0.000s
# e007.py
from __future__ import annotations
from itertools import count
from math import sqrt
import sys

def make_prime_table(N: int) -> list[int]:
    a = [True] * (N+1)
    M = int(sqrt(N+1))
    for p in range(2, M+1):
        if not a[p]:
            continue
        for n in range(p*p, N+1, p):
            a[n] = False
    
    ps = []
    for p in range(2, N+1):
        if a[p]:
            ps.append(p)
    return ps

def make_partial_prime_table(first: int, last: int) -> list[int]:
    N = last - first
    ps = make_prime_table(int(sqrt(last)))
    a = [True] * (N+1)
    for p in ps:
        n0 = max((first+p-1)//p*p, p*p)
        for n in range(n0, last, p):
            a[n-first] = False
    
    ps_partial = []
    for n in range(first, last):
        if a[n-first]:
            ps_partial.append(n)
    return ps_partial

def f(N: int) -> int:
    counter = 0
    for first in count(2, N):
        last = first + N
        ps = make_partial_prime_table(first, last)
        if counter + len(ps) >= N:
            return ps[N-counter-1]
        counter += len(ps)
    return counter

N = int(sys.argv[1])
print(f(N))
# e007.mojo
from math import max, sqrt
import sys

fn make_prime_table(N: Int) -> DynamicVector[Int]:
    let a = Pointer[Bool].alloc(N+1)
    for i in range(N+1):
        a.store(i, True)
    
    var p: Int = 2
    while p * p <= N:
        if not a.load(p):
            p += 1
            continue
        
        for n in range(p*p, N+1, p):
            a.store(n, False)
        p += 1
    
    var ps = DynamicVector[Int]()
    for n in range(2, N+1):
        if a.load(n):
            ps.push_back(n)
    a.free()
    return ps

fn make_partial_prime_table(first: Int, last: Int) -> DynamicVector[Int]:
    let N = last - first
    let ps = make_prime_table(Int(sqrt(last)))
    let a = Pointer[Bool].alloc(N)
    for i in range(N):
        a.store(i, True)
    
    for i in range(ps.size):
        let p = ps[i]
        let n0 = max((first+p-1)//p*p, p*p)
        for n in range(n0, last, p):
            a.store(n-first, False)
    
    var ps_partial = DynamicVector[Int]()
    for n in range(first, last):
        if a.load(n-first):
            ps_partial.push_back(n)
    a.free()
    return ps_partial

fn f(N: Int) -> Int:
    var counter: Int = 0
    var first: Int = 2
    while True:
        let last = first + N
        let ps = make_partial_prime_table(first, last)
        if counter + len(ps) >= N:
            return ps[N-counter-1]
        counter += ps.size
        first += N

fn main() raises:
    let args = sys.argv()
    let N = atol(args[1])
    print(f(N))
// e007.cpp
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<int> make_prime_table(size_t N) {
    vector<bool>    a(N+1, true);
    size_t  M = (size_t)sqrt(N+1.0);
    for(size_t p = 2; p <= M; ++p) {
        if(!a[p])
            continue;
        for(size_t n = p*p; n <= N; n += p)
            a[n] = false;
    }
    
    vector<int> ps;
    for(size_t n = 2; n <= N; ++n) {
        if(a[n])
            ps.push_back((int)n);
    }
    return ps;
}

vector<int> make_partial_prime_table(size_t first, size_t last) {
    const size_t    N = last - first;
    const auto  ps = make_prime_table((size_t)sqrt((double)last));
    vector<bool>    a(N, true);
    for(auto it = ps.begin(); it != ps.end(); ++it) {
        const size_t    p = (size_t)*it;
        const size_t    n0 = max((first+p-1)/p*p, p*p);
        for(size_t n = n0; n < last; n += p)
            a[n-first] = false;
    }
    
    vector<int> ps_partial;
    for(size_t n = first; n < last; ++n) {
        if(a[n-first])
            ps_partial.push_back((size_t)n);
    }
    return ps_partial;
}

int f(size_t N) {
    size_t counter = 0;
    for(size_t first = 2; ; first += N) {
        const size_t last = first + N;
        const auto  ps = make_partial_prime_table(first, last);
        if(counter + ps.size() >= N) {
            return ps[N-counter-1];
        }
        counter += ps.size();
    }
    return (int)counter;
}

int main(int argc, char **argv) {
    const size_t    N = (size_t)atol(argv[1]);
    cout << f(N) << endl;
}
// e007.rs
#![allow(non_snake_case)]

use std::cmp::max;
use std::env;


fn make_prime_table(N: usize) -> Vec<i32> {
    let mut a: Vec<bool> = vec![true; N+1];
    let M: usize = ((N+1) as f64).sqrt() as usize;
    for p in 2..M+1 {
        if !a[p] {
            continue
        }
        for n in (p*p..N+1).step_by(p) {
            a[n] = false
        }
    }
    
    let mut ps: Vec<i32> = vec![];
    for p in 2..N+1 {
        if a[p] {
            ps.push(p as i32)
        }
    }
    ps
}

fn make_partial_prime_table(first: usize, last: usize) -> Vec<i32> {
    let N = last - first;
    let ps = make_prime_table((last as f64).sqrt() as usize);
    let mut a: Vec<bool> = vec![true; N];
    for p in ps.into_iter() {
        let n0 = max(((first as i32)+p-1)/p*p, p*p) as usize;
        for n in (n0..last).step_by(p as usize) {
            a[n-first] = false
        }
    }
    
    let mut ps_partial: Vec<i32> = vec![];
    for n in first..last {
        if a[n-first] {
            ps_partial.push(n as i32)
        }
    }
    ps_partial
}

fn f(N: usize) -> i32 {
    let mut counter: usize = 0;
    for first in (2..).step_by(N) {
        let last = first + N;
        let ps = make_partial_prime_table(first, last);
        if counter + ps.len() >= N {
            return ps[N-counter-1]
        }
        counter += ps.len()
    }
    counter as i32
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let N: usize = args[1].parse().unwrap();
    println!("{}", f(N))
}