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)) }
