... I am trying to learn how to create modules and needed something to work on. ... create a module out of [this monstrosity] by doing the required changes, test the output by checking it ...

This seems like a reasonable way to learn about creating modules: start with a lousy algorithm, create a MyModule.pm that exports something like is_prime(), create a MyModule.t for the module to test its correct operation (and which can also test execution time), then start improving the algorithm to exercise the process of developing, improving and maintaining the module.

Ok, you've got the lousy algorithm. So where's the module and its .t script? That seems to me to be the thing to focus on right now. (There are even some who say that one should write the .t script before writing the module!) Believe me, you'll find plenty of ways to improve and extend things once you've got the algorithm encapsulated in a module along with a .t script for it, i.e., once the interface is defined and testable. Interface definition and creation of a testing environment is the first step. Go for it. But at this stage, why are you worrying about better algorithms?