user
The   **totient**   function is also known as:

:   :   * Euler's totient function
        * Euler's phi totient function
        * phi totient function
        * Φ    function   (uppercase Greek phi)
        * φ     function   (lowercase Greek phi)

Definitions   (as per number theory)

The totient function:

:   :   * counts the integers up to a given positive integer   **n**   that are relatively prime to   **n**
        * counts the integers   **k**   in the range   **1 ≤ k ≤ n**   for which the greatest common divisor   **gcd(n,k)**   is equal to   **1**
        * counts numbers   **≤ n**   and   prime to   **n**

If the totient number   (for **N**)   is one less than   **N**,   then   **N**   is prime.

Task

Create a   **totient**   function and:

:   :   * Find and display   (1 per line)   for the 1st   **25**   integers:

        :   :   * the integer   (the index)
                * the totient number for that integer
                * indicate if that integer is prime

        * Find and display the   *count*   of the primes up to          100
        * Find and display the   *count*   of the primes up to       1,000
        * Find and display the   *count*   of the primes up to     10,000
        * Find and display the   *count*   of the primes up to   100,000     (optional)

Show all output here.

Related task
:   :   * Perfect totient numbers

Also see
:   :   * Wikipedia: Euler's totient function.
        * MathWorld: totient function.
        * OEIS: Euler totient function phi(n).
assistant
(formerly Perl 6)

**Works with**: Rakudo version 2018.11

This is an *incredibly* inefficient way of finding prime numbers.

```
use Prime::Factor;

my \𝜑 = 0, |(1..*).hyper.map: -> \t { t * [*] t.&prime-factors.squish.map: { 1 - 1/$_ } }

printf "𝜑(%2d) = %3d %s\n", $_, 𝜑[$_], $_ - 𝜑[$_] - 1 ?? '' !! 'Prime' for 1 .. 25;

(1e2, 1e3, 1e4, 1e5).map: -> $limit {
    say "\nCount of primes <= $limit: " ~ +(^$limit).grep: {$_ == 𝜑[$_] + 1}
}

```

Output:

```
𝜑( 1) =   1
𝜑( 2) =   1 Prime
𝜑( 3) =   2 Prime
𝜑( 4) =   2
𝜑( 5) =   4 Prime
𝜑( 6) =   2
𝜑( 7) =   6 Prime
𝜑( 8) =   4
𝜑( 9) =   6
𝜑(10) =   4
𝜑(11) =  10 Prime
𝜑(12) =   4
𝜑(13) =  12 Prime
𝜑(14) =   6
𝜑(15) =   8
𝜑(16) =   8
𝜑(17) =  16 Prime
𝜑(18) =   6
𝜑(19) =  18 Prime
𝜑(20) =   8
𝜑(21) =  12
𝜑(22) =  10
𝜑(23) =  22 Prime
𝜑(24) =   8
𝜑(25) =  20

Count of primes <= 100: 25

Count of primes <= 1000: 168

Count of primes <= 10000: 1229

Count of primes <= 100000: 9592
```