in reply to
Why is this code so much slower than the same algorithm in C?
Short answer: Perl is an interpreted language and C is a compiled language.
Long answer: Perl code is executed by a virtual machine that is itself a binary executable for the native hardware of the host. C code is compiled to a binary executable for the native hardware of the host. That extra layer of software is inefficient. Perhaps the surprising thing is how often that inefficiency is irrelevant. It tends to become irrelevant when interacting with users, doing file I/O, doing almost anything with a network, and in a variety of other situations. Where it is relevant is in tasks that are purely CPU intensive, like that presented in your code.