Task — Prime order

You are given an array of unique positive integers greater than 2. Write a script to sort them in ascending order of the count of their prime factors, tie-breaking by ascending value.

Examples

Example 1
Input: @int = (11, 8, 27, 4)
Output: (11, 4, 8, 27))

Prime factors of 11 => 11
Prime factors of  4 => 2, 2
Prime factors of  8 => 2, 2, 2
Prime factors of 27 => 3, 3, 3

Analysis

This task divides into two subtasks: find the prime factors of each number and then list the numbers in the specified order.

No doubt there are CPAN modules to find the prime factors, but it is isn't a hard task so I did it from scratch. To start with, I create a sieve of Eratosthenes up to the largest value in @int. My sieve is stored such that $sieve[$i] is 1 if $i is prime and 0 if it isn't.

Now I can find the prime factors of any number by dividing it repeatedly by each of my primes, and recording the divisions that yield no remainder - or more practically, where the quotient is not an integer.

So how to list them in the prescribed order? Perl doesn't have a built-in sort on multiple keys, but a practical way round this is to create a text key composed from all the actual keys and use that in a hash. In this case I created a key like this:

00000003-00000012

where the first group of 8 digits is the number of prime factors and the second group is the original number from @int: in this example, 12 is 2 x 2 x 3, so it has 3 prime factors

Conveniently I can use the value of the hash element to be the list of the factors:

$output{'00000003-00000012'} = '2, 2, 3';

Now I can do a simple

for $k (sort keys %output)

loop which will give me the results in the right order - sorted first by number of factors and then by the original number. I split the key into its two components and use the second component (12 in this case) as the next number in the output list, and use the hash value ('2, 2, 3') in the explanatory lines shown after the output.

Try it 

Try running the script with any input:

Your @int =

example: 118, 256, 343, 888, 765

⤡

#!/usr/bin/perl

use v5.16;    # The Weekly Challenge - 2023-10-30
use utf8;     # Week 241 task 2 - Prime order
use strict;   # Peter Campbell Smith
use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

my (@sieve, $j, @int, $next, $count, @used);

prime_order(11, 8, 27, 4);

# bigger example: 30 unique numbers in (2 .. 500)
$count = 0;
while ($count < 30) {
    $next = int(rand(501));
    next if $used[$next] or $next < 2;
    push(@int, $next);
    $count ++;
    $used[$next] = 1;
}
prime_order(@int);  

sub prime_order {
    
    my (@int, $largest, $i, $count, $list, %output, $k, $explain, $ordered);
    
    # initialise
    @int = @_;
    
    # find the largest and create sieve of Eratosthenes
    $largest = 0;
    for $i (@int) {
        $largest = $i if $i > $largest;
    }
    make_sieve($largest);
    
    # loop over @int, get prime factors and provide key to sort in desired order
    for ($i = 0; $i < @int; $i ++) {
        ($count, $list) = prime_factors($int[$i]);
        $output{sprintf('%08d~%08d', $count, $int[$i])} = $list;
    }
    
    # extract sorted results and prepare to display
    $explain = '';
    $ordered = '';
    for $k (sort keys %output) {
        $k =~ m|(\d+)~(\d+)|;
        $i = $2 + 0;
        $ordered .= qq[$i, ];
        $explain .= sprintf(qq[         Prime factors of %3d => %s\n], $i, $output{$k});
    }
            
    # show results
    say qq[\nInput:  \@int = (] . join(q[, ], @int) . q[)];
    say qq[Output: (], substr($ordered, 0, -2) . ')';
    say substr($explain, 0, -1); 
}

sub make_sieve {

    my ($arg, $j, $k);
    
    # set all values provisionally to 1 (ie prime)
    $arg = shift;
    for $j (0 .. $arg) {
        $sieve[$j] = 1;
    }

    # for each prime in turn, set its multiples to 0 (ie not prime)
    for $j (2 .. $arg) {
        next unless $sieve[$j];   # $j is not prime
        last if $j ** 2 > $arg;
        for $k ($j .. $arg) {
            last if $k * $j > $arg;
            $sieve[$k * $j] = 0;
        }
    }
}

sub prime_factors {
    
    # returns count and list of prime factors
    
    my ($arg, $pf, $count, $list, $q, $prime);
    
    # initialise
    $arg = shift;
    $pf = '';
    $count = 0;
    $list = '';
    
    # loop over all primes <= input
    for $prime (2 .. $arg) {
        next unless $sieve[$prime];
        
        # try dividing remaining number repeatedly by each prime
        while (1) {
            $q = $arg / $prime;
            
            # found a prime factor - add to count and list
            if ($q == int($q)) {
                $count ++;
                $list .= qq[$prime, ];
                $arg = $q;
                
            # no more of this prime
            } else {
                last;
            }
        }
    }
    return ($count, substr($list, 0, -2));
}
    

Output

Input:  @int = (11, 8, 27, 4)
Output: (11, 4, 8, 27)
         Prime factors of  11 => 11
         Prime factors of   4 => 2, 2
         Prime factors of   8 => 2, 2, 2
         Prime factors of  27 => 3, 3, 3

Input:  @int = (75, 160, 407, 357, 292, 417, 370, 248, 83, 299, 50, 319, 426, 343, 94, 404, 239, 91, 106, 295, 352, 419, 410, 154, 151, 145, 325, 333, 25, 201)
Output: (83, 151, 239, 419, 25, 91, 94, 106, 145, 201, 295, 299, 319, 407, 417, 50, 75, 154, 292, 325, 333, 343, 357, 370, 404, 410, 426, 248, 160, 352)
         Prime factors of  83 => 83
         Prime factors of 151 => 151
         Prime factors of 239 => 239
         Prime factors of 419 => 419
         Prime factors of  25 => 5, 5
         Prime factors of  91 => 7, 13
         Prime factors of  94 => 2, 47
         Prime factors of 106 => 2, 53
         Prime factors of 145 => 5, 29
         Prime factors of 201 => 3, 67
         Prime factors of 295 => 5, 59
         Prime factors of 299 => 13, 23
         Prime factors of 319 => 11, 29
         Prime factors of 407 => 11, 37
         Prime factors of 417 => 3, 139
         Prime factors of  50 => 2, 5, 5
         Prime factors of  75 => 3, 5, 5
         Prime factors of 154 => 2, 7, 11
         Prime factors of 292 => 2, 2, 73
         Prime factors of 325 => 5, 5, 13
         Prime factors of 333 => 3, 3, 37
         Prime factors of 343 => 7, 7, 7
         Prime factors of 357 => 3, 7, 17
         Prime factors of 370 => 2, 5, 37
         Prime factors of 404 => 2, 2, 101
         Prime factors of 410 => 2, 5, 41
         Prime factors of 426 => 2, 3, 71
         Prime factors of 248 => 2, 2, 2, 31
         Prime factors of 160 => 2, 2, 2, 2, 2, 5
         Prime factors of 352 => 2, 2, 2, 2, 2, 11