I did a straight port of C to lua, and ran it with luajit.
The C code ran in 49.901s.
The luajit code ran in 14m16.547s.
C code was compiled with -02 -std=c11 -lm (version 4.8.1, mingw).
luajit.exe was 2.0.3, static build, using VS2012 x64
"The luajit code ran in 856.547s."
The graph is log-log which can be a bit tricky to read but that puts it in the same ballpark as Ruby and PHP (assuming the same factor of difference between the two, after scaling your C vs luajit results to match the given C value of ~40s, luajit becomes 687s.)
* Oops, I had cheated and used a for loop instead of while. The LuaJIT time was the same but the others are 10.5x, 12.58x, 15.63x.
Edit: fixed luajit version
If you see anything wrong with it, or odd, feel free to share.
I'm still investigating what is happening to make the run so slow, so if you can find something wrong in my code, that would help.
Replacing math.mod(n, i) with (n % i) gives roughly 9.4x performance.
EDIT: luajit version was LuaJIT 2.0.4 on Mac OSX