Java doesn't have any optimization flags and the debugging info slowdown makes sense I suppose. That is the exact difference between them, GCC with -O3 is almost 100x faster in another test I just did: 10s for Java, 0.1 for C. When you turn off the optimization flags C jumps right at the same 10s figure though.
Really cool interesting stuff!