The weekly challenge 241 - Task 2: Prime Order

 1 #!/usr/bin/perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-241/#TASK2
 3 #
 4 # Task 2: Prime Order
 5 # ===================
 6 #
 7 # You are given an array of unique positive integers greater than 2.
 8 #
 9 # Write a script to sort them in ascending order of the count of their prime
10 # factors, tie-breaking by ascending value.
11 #
12 ## Example 1
13 ##
14 ## Input: @int = (11, 8, 27, 4)
15 ## Output: (11, 4, 8, 27))
16 ##
17 ## Prime factors of 11 => 11
18 ## Prime factors of  4 => 2, 2
19 ## Prime factors of  8 => 2, 2, 2
20 ## Prime factors of 27 => 3, 3, 3
21 #
22 ############################################################
23 ##
24 ## discussion
25 ##
26 ############################################################
27 #
28 # Sort by number of prime factors first, then by the number
29 # itself second.
30 # We calculate the number of prime factors in an extra recursive
31 # function, using a cache of already calculated numbers to mitigate
32 # unnecessary recalculations
33 #
34 use strict;
35 use warnings;
36 
37 prime_order(11, 8, 27, 4);
38 
39 sub prime_order {
40    my @int = @_;
41    print "Input: (" . join(", ", @int) . ")\n";
42    my @result = sort { prime_factor_count($a) <=> prime_factor_count($b) || $a <=> $b } @int;
43    print "Output: (" . join(", ", @result) . ")\n";
44 }
45 
46 {
47    my $cache = {};
48    sub prime_factor_count {
49       my $number = shift;
50       my $count = 0;
51       unless($cache->{$number}) {
52          foreach my $i (2..$number) {
53             if($number % $i == 0) {
54                $count = 1 + prime_factor_count($number / $i);
55                last;
56             }
57          }
58          $cache->{$number} = $count;
59       }
60 
61       return $cache->{$number};
62    }
63 }