laurent_r

These are some answers to the Week 82 of the Perl Weekly Challenge organized by Mohammad S. Anwar

On Friday, Oct. 16, 2020 around 5:00 p.m., an awful terrorist attack was perpetrated in my home-town of Conflans Sainte-Honorine in France (35,000 inhabitants), the city where I live and of which I am a city councilor. A secondary school teacher was beheaded by a crazy religious extremist who coudn’t accept that teacher’s defense of the freedom of speech. This is a terrible shock to all my fellow citizens, to the teachers and pupils of that school, and to my fellow members of the city council. Because of that, I did not have time to complete the second task of this challenge (although it was almost complete) and my blog post on the first task will be shorter than what I wanted to make. I actually considered not publishing a blog post this week, but I have written at least one blog post for every single Perl Weekly Challenge since the very beginning, I certainly do not want a madman to prevent me from continuing this uninterrupted series of blogs on PWC. And I also don’t want to leave my friend Mohammad S. Anwar alone in the cold.

Common Factors

You are given 2 positive numbers $M and $N.

Write a script to list all common factors of the given numbers.

Example 1:

Input:
    $M = 12
    $N = 18

Output:
    (1, 2, 3, 6)

Explanation:
    Factors of 12: 1, 2, 3, 4, 6
    Factors of 18: 1, 2, 3, 6, 9

Example 2:

Input:
    $M = 18
    $N = 23

Output:
    (1)

Explanation:
    Factors of 18: 1, 2, 3, 6, 9
    Factors of 23: 1

I wanted to give some more explanations, but the short version is that the common factors of two numbers are the factors of the greatest common divisor (GCD) of the two input numbers. So we will compute the GCD of the two numbers and find its divisors.

Common Factors in Raku

Raku has a built-in operator, gcd, to compute the GCD of two numbers.

The code is thus quite simple:

sub common_factors (Int $a, Int $b) {
    my $gcd = $a gcd $b;
    return (1,) if $gcd == 1;
    return ($gcd,) if $gcd.is-prime;
    return (1..$gcd).grep($gcd %% *).unique;
}
my @result = common_factors 12, 18;
say @result;

Output:

raku common_factors.raku
[1 2 3 6]

Common Factors in Perl

Perl doesn’t have a built-in GCD routine. So we will write one using Euclid’s algorithm, or, rather, a modernized version of his algorithm using the % modulo operator, rather than subtraction in the original version of Euclid’s algorithm.

use strict;
use warnings;
use feature "say";

sub gcd {
    my ($i, $j) = sort { $a <=> $b } @_;
    while ($j) {
        ($i, $j) = ($j, $i % $j);
    }
    return $i;
}

sub common_factors {
    my ($i, $j) = @_;
    my $gcd = gcd ($i, $j);
    return (1) if $gcd == 1;
    my @factors = grep { $gcd % $_ == 0 } 1..$gcd; 
    my %unique = map {$_ => 1} @factors;
    return sort { $a <=> $b } keys %unique;
}
say join " ", common_factors @ARGV;

Output:

$ perl common_factors.pl 12 18
1 2 3 6

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, October 25, 2020. And, please, also spread the word about the Perl Weekly Challenge if you can.