Triplets and factors

Weekly challenge 241 — 30 October 2023

Week 241 - 30 Oct 2023

Task 2

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.

Example 1Input: @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

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.

#!/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)); }

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

Peter Campbell Smith is hereby placed in the public domain