DEV Community

Discussion on: Daily Challenge #78 - Number of Proper Fractions with Denominator d

View post
Collapse
 
choroba profile image
E. Choroba •

The number of proper fractions is the number of numbers in 1 .. N-1 that are coprime with N, i.e. whose greatest common divisor with N is 1.

#!/usr/bin/perl
use warnings;
use strict;

sub gcd {
    my ($x, $y) = @_;
    ($x, $y) = ($y, $x) if $x > $y;

    return $y unless $x;

    return gcd($y - ($x * int($y / $x)), $x)
}

sub proper_fractions {
    my ($n) = @_;
    grep 1 == gcd($n, $_), 1 .. $n - 1
}

use Test::More tests => 5;

is proper_fractions(1), 0;
is proper_fractions(2), 1;
is proper_fractions(5), 4;
is proper_fractions(15), 8;
is proper_fractions(25), 20;