Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Tree: 7d9c16311e
Fetching contributors…

Cannot retrieve contributors at this time

50 lines (37 sloc) 1.344 kB
use v6;
# Specification:
# P34 (**) Calculate Euler's totient function phi(m).
# Euler's so-called totient function phi(m) is defined as the number of
# positive integers r (1 <= r < m) that are coprime to m.
# Example:
# m = 10: r = 1,3,7,9; thus phi(m) = 4. Note the special case: phi(1) = 1.
# > say totient_phi 10
# 4
#
# Find out what the value of phi(m) is if m is a prime number. Euler's totient
# function plays an important role in one of the most widely used public key
# cryptography methods (RSA). In this exercise you should use the most
# primitive method to calculate this function (there are smarter ways that we
# shall discuss later).
# from P32-rhebus.pl
sub gcds (Int $a, Int $b) {
return ($a, $b, *%* ... 0)[*-2];
}
# from P33-rhebus.pl
our sub infix:<coprime> (Int $a, Int $b) { gcds($a,$b) == 1 }
# Example 1: iteration
multi totient_phi_i (1 --> Int) { 1 }
multi totient_phi_i (Int $n --> Int) {
my $total = 0;
for 1..^$n -> $k { $total++ if $n coprime $k }
return $total;
}
say "phi($_): ", totient_phi_i $_ for (1..20);
# Example 2: «coprime« hyper operator
multi totient_phi (1 --> Int) { 1 }
multi totient_phi (Int $n --> Int) {
return 1 if $n ~~ 1;
return [+] ($n «coprime« list(1..^$n));
}
say "phi($_): ",totient_phi $_ for (1..20);
# vim:ft=perl6
Jump to Line
Something went wrong with that request. Please try again.