LuaJIT 2.0.4: 3.67user 0.01system 0:03.68elapsed 99%CPU rustc 1.9.0-nightly (74b886ab1 2016-03-13) (-C opt-level=3): 5.18user 0.00system 0:05.20elapsed 99%CP

LuaJIT 2.0.4: 3.67user 0.01system 0:03.68elapsed 99%CPU rustc 1.9.0-nightly (74b886ab1 2016-03-13) (-C opt-level=3): 5.18user 0.00system 0:05.20elapsed 99%CPU Switching to BTreeMap gives me: 4.36user 0.00system 0:04.38elapsed 99%CPU Using u8 as the key (last_digit0*10 + last_digit1) instead of a string: 4.18user 0.00system 0:04.18elapsed 99%CPU I tried preallocating the vector of primes and it didn't help, strangely enough. Replacing the floating-point sqrt with squaring in the comparison does bring it a bit lower: 4.04user 0.00system 0:04.05elapsed 99%CPU I don't know how to bring that number lower without using a sieve, perf reports that most of the time is spent in: 86,31 │ div %rbx I've also just noticed that the Lua and the Rust code don't give the same results, but I can't easily tell why. Oh! The largest prime is 0x00ec4bab, so they can be stored as u32. Final Rust result: 2.33user 0.00system 0:02.33elapsed 99%CPU Code: https://gist.github.com/eddyb/51a92fa2edf20d6e23fe https://gist.github.com/eddyb/51a92fa2edf20d6e23fe