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