This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)
Task #2 this week asks us to calculate a so called Home prime. Home primes are found by factoring a number and concatenating the prime factors (including powers, so 20 = 5×2×2), and repeating this until the result is a prime number.
The given example, HP(10) can be found via the following steps: HP(10) = HP(25) = HP(55) = HP(511) = HP(773), and we stop, since 773 is a prime number.
This is a natural problem for recursion:
sub home_prime_recursive { my @fac = factor($_[0]); @fac == 1 ? $_[0] : home_prime(join '', @fac);} |
I like this solution for its expressiveness, but it’s about 20% slower than the following iterative version:
sub home_prime_iterative { my $n = shift; while ((my @fac = factor($n)) > 1) { $n = join '', @fac; } return $n;} |
Note that the logic is identical between the two examples; it’s just expressed as a loop conditional and jump versus a conditional and tail call in the preceding example. The difference in performance is down to Perl’s stack and function call overhead. Even using goto &home_prime to manually enforce tail call optimization resulted in zero speedup from the above recursive solution. Language quirks like this don’t matter 90% of the time, but it pays to keep them in the back of your mind for the 10% of cases that need to be optimized.
Raku
Extremely similar to the recursive Perl version.
use Prime::Factor;sub home_prime($n) { my @fac = prime-factors($n); @fac.elems == 1 ?? $n !! home_prime(@fac.join);} |