I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Totient function

Totient function
You are encouraged to solve this task according to the task description, using any language you may know.

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.

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.

Also see

## 11l

Translation of: Python
`F f(n)   R sum((1..n).filter(k -> gcd(@n, k) == 1).map(k -> 1)) F is_prime(n)   R f(n) == n - 1 L(n) 1..25   print(‘ f(#.) == #.’.format(n, f(n))‘’(I is_prime(n) {‘, is prime’} E ‘’))V count = 0L(n) 1..10'000   count += is_prime(n)   I n C (100, 1000, 10'000)      print(‘Primes up to #.: #.’.format(n, count))`
Output:
``` f(1) == 1
f(2) == 1, is prime
f(3) == 2, is prime
f(4) == 2
f(5) == 4, is prime
f(6) == 2
f(7) == 6, is prime
f(8) == 4
f(9) == 6
f(10) == 4
f(11) == 10, is prime
f(12) == 4
f(13) == 12, is prime
f(14) == 6
f(15) == 8
f(16) == 8
f(17) == 16, is prime
f(18) == 6
f(19) == 18, is prime
f(20) == 8
f(21) == 12
f(22) == 10
f(23) == 22, is prime
f(24) == 8
f(25) == 20
Primes up to 100: 25
Primes up to 1000: 168
Primes up to 10000: 1229
```

Translation of: C
`with Ada.Text_IO;with Ada.Integer_Text_IO; procedure Totient is    function Totient (N : in Integer) return Integer is      Tot : Integer := N;      I   : Integer;      N2  : Integer := N;   begin      I := 2;      while I * I <= N2 loop         if N2 mod I = 0 then            while N2 mod I = 0 loop               N2 := N2 / I;            end loop;            Tot := Tot - Tot / I;         end if;          if I = 2 then            I := 1;         end if;         I := I + 2;      end loop;       if N2 > 1 then         Tot := Tot - Tot / N2;      end if;       return Tot;   end Totient;    Count : Integer := 0;   Tot   : Integer;   Placeholder : String := "  n  Phi  Is_Prime";   Image_N     : String renames Placeholder ( 1 ..  3);   Image_Phi   : String renames Placeholder ( 6 ..  8);   Image_Prime : String renames Placeholder (11 .. 17);   use Ada.Text_IO;   use Ada.Integer_Text_IO;begin    Put_Line (Placeholder);    for N in 1 .. 25 loop      Tot := Totient (N);       if N - 1 = Tot then         Count := Count + 1;      end if;      Put (Image_N, N);      Put (Image_Phi, Tot);      Image_Prime := (if N - 1 = Tot then "    True" else "   False");      Put_Line (Placeholder);   end loop;   New_Line;    Put_Line ("Number of primes up to " & Integer'(25)'Image &" =" & Count'Image);    for N in 26 .. 100_000 loop      Tot := Totient (N);       if Tot = N - 1 then         Count := Count + 1;      end if;       if N = 100 or N = 1_000 or N mod 10_000 = 0 then         Put_Line ("Number of primes up to " & N'Image & " =" & Count'Image);      end if;   end loop; end Totient;`
Output:
```  n  Phi  Is_Prime
1    1     False
2    1      True
3    2      True
4    2     False
5    4      True
6    2     False
7    6      True
8    4     False
9    6     False
10    4     False
11   10      True
12    4     False
13   12      True
14    6     False
15    8     False
16    8     False
17   16      True
18    6     False
19   18      True
20    8     False
21   12     False
22   10     False
23   22      True
24    8     False
25   20     False

Number of primes up to  25 = 9
Number of primes up to  100 = 25
Number of primes up to  1000 = 168
Number of primes up to  10000 = 1229
Number of primes up to  20000 = 2262
Number of primes up to  30000 = 3245
Number of primes up to  40000 = 4203
Number of primes up to  50000 = 5133
Number of primes up to  60000 = 6057
Number of primes up to  70000 = 6935
Number of primes up to  80000 = 7837
Number of primes up to  90000 = 8713
Number of primes up to  100000 = 9592```

## ALGOL 68

Translation of: Go

Uses the totient algorithm from the second Go sample.

`BEGIN    # returns the number of integers k where 1 <= k <= n that are mutually prime to n #    PROC totient = ( INT n )INT:        IF   n < 3 THEN 1        ELIF n = 3 THEN 2        ELSE            INT result := n;            INT v      := n;            INT i      := 2;            WHILE i * i <= v DO                IF v MOD i = 0 THEN                    WHILE v MOD i = 0 DO v OVERAB i OD;                    result -:= result OVER i                FI;                IF i = 2 THEN                   i := 1                FI;                i +:= 2            OD;            IF v > 1 THEN result -:= result OVER v FI;            result         FI # totient # ;    # show the totient function values for the first 25 integers #    print( ( " n  phi(n) remarks", newline ) );    FOR n TO 25 DO        INT tn = totient( n );        print( ( whole( n, -2 ), ": ", whole( tn, -5 ), IF tn = n - 1 AND tn /= 0 THEN "  n is prime" ELSE "" FI, newline ) )    OD;    # use the totient function to count primes #    INT n100 := 0, n1000 := 0, n10000 := 0, n100000 := 0;    FOR n TO 100 000 DO        IF totient( n ) = n - 1 THEN            IF n <=     100 THEN    n100 +:= 1 FI;            IF n <=   1 000 THEN   n1000 +:= 1 FI;            IF n <=  10 000 THEN  n10000 +:= 1 FI;            IF n <= 100 000 THEN n100000 +:= 1 FI        FI    OD;    print( ( "There are ", whole(    n100, -6 ), " primes below      100", newline ) );    print( ( "There are ", whole(   n1000, -6 ), " primes below    1 000", newline ) );    print( ( "There are ", whole(  n10000, -6 ), " primes below   10 000", newline ) );    print( ( "There are ", whole( n100000, -6 ), " primes below  100 000", newline ) )END`
Output:
``` n  phi(n) remarks
1:     1
2:     1  n is prime
3:     2  n is prime
4:     2
5:     4  n is prime
6:     2
7:     6  n is prime
8:     4
9:     6
10:     4
11:    10  n is prime
12:     4
13:    12  n is prime
14:     6
15:     8
16:     8
17:    16  n is prime
18:     6
19:    18  n is prime
20:     8
21:    12
22:    10
23:    22  n is prime
24:     8
25:    20
There are     25 primes below      100
There are    168 primes below    1 000
There are   1229 primes below   10 000
There are   9592 primes below  100 000
```

## APL

Works with: Dyalog APL
`task←{    totient ← 1+.=⍳∨⊢    prime   ← totient=-∘1     ⎕←'Index' 'Totient' 'Prime',(⊢⍪totient¨,[÷2]prime¨)⍳25    {⎕←'There are' (+/prime¨⍳⍵) 'primes below' ⍵}¨100 1000 10000}`
Output:
``` Index    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Totient  1 1 2 2 4 2 6 4 6  4 10  4 12  6  8  8 16  6 18  8 12 10 22  8 20
Prime    0 1 1 0 1 0 1 0 0  0  1  0  1  0  0  0  1  0  1  0  0  0  1  0  0
There are  25  primes below  100
There are  168  primes below  1000
There are  1229  primes below  10000```

## AWK

` # syntax: GAWK -f TOTIENT_FUNCTION.AWKBEGIN {    print(" N Phi isPrime")    for (n=1; n<=1000000; n++) {      tot = totient(n)      if (n-1 == tot) {        count++      }      if (n <= 25) {        printf("%2d %3d %s\n",n,tot,(n-1==tot)?"true":"false")        if (n == 25) {          printf("\n  Limit PrimeCount\n")          printf("%7d %10d\n",n,count)        }      }      else if (n ~ /^100+\$/) {        printf("%7d %10d\n",n,count)      }    }    exit(0)}function totient(n,  i,tot) {    tot = n    for (i=2; i*i<=n; i+=2) {      if (n % i == 0) {        while (n % i == 0) {          n /= i        }        tot -= tot / i      }      if (i == 2) {        i = 1      }    }    if (n > 1) {      tot -= tot / n    }    return(tot)} `
Output:
``` N Phi isPrime
1   1 false
2   1 true
3   2 true
4   2 false
5   4 true
6   2 false
7   6 true
8   4 false
9   6 false
10   4 false
11  10 true
12   4 false
13  12 true
14   6 false
15   8 false
16   8 false
17  16 true
18   6 false
19  18 true
20   8 false
21  12 false
22  10 false
23  22 true
24   8 false
25  20 false

Limit PrimeCount
25          9
100         25
1000        168
10000       1229
100000       9592
1000000      78498
```

## C

Translation of the second Go example

` /*Abhishek Ghosh, 7th December 2018*/ #include<stdio.h> int totient(int n){	int tot = n,i; 	for(i=2;i*i<=n;i+=2){		if(n%i==0){			while(n%i==0)				n/=i;			tot-=tot/i;		} 		if(i==2)			i=1;	} 	if(n>1)		tot-=tot/n; 	return tot;} int main(){	int count = 0,n,tot; 	printf(" n    %c   prime",237);        printf("\n---------------\n"); 	for(n=1;n<=25;n++){		tot = totient(n); 		if(n-1 == tot)			count++; 		printf("%2d   %2d   %s\n", n, tot, n-1 == tot?"True":"False");	} 	printf("\nNumber of primes up to %6d =%4d\n", 25,count); 	for(n = 26; n <= 100000; n++){        tot = totient(n);        if(tot == n-1)			count++;         if(n == 100 || n == 1000 || n%10000 == 0){            printf("\nNumber of primes up to %6d = %4d\n", n, count);        }    } 	return 0;} `

Output :

``` n    φ   prime
---------------
1    1   False
2    1   True
3    2   True
4    2   False
5    4   True
6    2   False
7    6   True
8    4   False
9    6   False
10    4   False
11   10   True
12    4   False
13   12   True
14    6   False
15    8   False
16    8   False
17   16   True
18    6   False
19   18   True
20    8   False
21   12   False
22   10   False
23   22   True
24    8   False
25   20   False

Number of primes up to     25 =   9

Number of primes up to    100 =   25

Number of primes up to   1000 =  168

Number of primes up to  10000 = 1229

Number of primes up to  20000 = 2262

Number of primes up to  30000 = 3245

Number of primes up to  40000 = 4203

Number of primes up to  50000 = 5133

Number of primes up to  60000 = 6057

Number of primes up to  70000 = 6935

Number of primes up to  80000 = 7837

Number of primes up to  90000 = 8713

Number of primes up to 100000 = 9592
```

## C#

`using static System.Console;using static System.Linq.Enumerable; public class Program{    static void Main()    {        for (int i = 1; i <= 25; i++) {            int t = Totient(i);            WriteLine(i + "\t" + t + (t == i - 1 ? "\tprime" : ""));        }        WriteLine();        for (int i = 100; i <= 100_000; i *= 10) {            WriteLine(\$"{Range(1, i).Count(x => Totient(x) + 1 == x):n0} primes below {i:n0}");        }    }     static int Totient(int n) {        if (n < 3) return 1;        if (n == 3) return 2;         int totient = n;         if ((n & 1) == 0) {            totient >>= 1;            while (((n >>= 1) & 1) == 0) ;        }         for (int i = 3; i * i <= n; i += 2) {            if (n % i == 0) {                totient -= totient / i;                while ((n /= i) % i == 0) ;            }        }        if (n > 1) totient -= totient / n;        return totient;    }}`
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

25 primes below 100
168 primes below 1,000
1,229 primes below 10,000
9,592 primes below 100,000
```

## C++

Translation of: Java
`#include <cassert>#include <iomanip>#include <iostream>#include <vector> class totient_calculator {public:    explicit totient_calculator(int max) : totient_(max + 1) {        for (int i = 1; i <= max; ++i)            totient_[i] = i;        for (int i = 2; i <= max; ++i) {            if (totient_[i] < i)                continue;            for (int j = i; j <= max; j += i)                totient_[j] -= totient_[j] / i;        }    }    int totient(int n) const {        assert (n >= 1 && n < totient_.size());        return totient_[n];    }    bool is_prime(int n) const {        return totient(n) == n - 1;    }private:    std::vector<int> totient_;}; int count_primes(const totient_calculator& tc, int min, int max) {    int count = 0;    for (int i = min; i <= max; ++i) {        if (tc.is_prime(i))            ++count;    }    return count;} int main() {    const int max = 10000000;    totient_calculator tc(max);    std::cout << " n  totient  prime?\n";    for (int i = 1; i <= 25; ++i) {        std::cout << std::setw(2) << i            << std::setw(9) << tc.totient(i)            << std::setw(8) << (tc.is_prime(i) ? "yes" : "no") << '\n';    }    for (int n = 100; n <= max; n *= 10) {        std::cout << "Count of primes up to " << n << ": "            << count_primes(tc, 1, n) << '\n';    }    return 0;}`
Output:
``` n  totient  prime?
1        1      no
2        1     yes
3        2     yes
4        2      no
5        4     yes
6        2      no
7        6     yes
8        4      no
9        6      no
10        4      no
11       10     yes
12        4      no
13       12     yes
14        6      no
15        8      no
16        8      no
17       16     yes
18        6      no
19       18     yes
20        8      no
21       12      no
22       10      no
23       22     yes
24        8      no
25       20      no
Count of primes up to 100: 25
Count of primes up to 1000: 168
Count of primes up to 10000: 1229
Count of primes up to 100000: 9592
Count of primes up to 1000000: 78498
Count of primes up to 10000000: 664579
```

## D

Translation of: C
`import std.stdio; int totient(int n) {    int tot = n;     for (int i = 2; i * i <= n; i += 2) {        if (n % i == 0) {            while (n % i == 0) {                n /= i;            }            tot -= tot / i;        }        if (i==2) {            i = 1;        }    }     if (n > 1) {        tot -= tot / n;    }    return tot;} void main() {    writeln(" n    φ   prime");    writeln("---------------");     int count = 0;    for (int n = 1; n <= 25; n++) {        int tot = totient(n);         if (n - 1 == tot) {            count++;        }         writefln("%2d   %2d   %s", n,tot, n - 1 == tot);    }    writeln;     writefln("Number of primes up to %6d = %4d", 25, count);    for (int n = 26; n <= 100_000; n++) {        int tot = totient(n);         if (n - 1 == tot) {            count++;        }         if (n == 100 || n == 1_000 || n % 10_000 == 0) {            writefln("Number of primes up to %6d = %4d", n, count);        }    }}`
Output:
``` n    φ   prime
---------------
1    1   false
2    1   true
3    2   true
4    2   false
5    4   true
6    2   false
7    6   true
8    4   false
9    6   false
10    4   false
11   10   true
12    4   false
13   12   true
14    6   false
15    8   false
16    8   false
17   16   true
18    6   false
19   18   true
20    8   false
21   12   false
22   10   false
23   22   true
24    8   false
25   20   false

Number of primes up to     25 =    9
Number of primes up to    100 =   25
Number of primes up to   1000 =  168
Number of primes up to  10000 = 1229
Number of primes up to  20000 = 2262
Number of primes up to  30000 = 3245
Number of primes up to  40000 = 4203
Number of primes up to  50000 = 5133
Number of primes up to  60000 = 6057
Number of primes up to  70000 = 6935
Number of primes up to  80000 = 7837
Number of primes up to  90000 = 8713
Number of primes up to 100000 = 9592```

See Pascal.

## Dyalect

Translation of: Go
`func totient(n) {    var tot = n    var i = 2    while i * i <= n {        if n % i == 0 {            while n % i == 0 {                n /= i            }            tot -= tot / i        }        if i == 2 {            i = 1        }        i += 2    }    if n > 1 {        tot -= tot / n    }    return tot}  print("n\tphi\tprime")var count = 0for n in 1..25 {    var tot = totient(n)    var isPrime = n - 1 == tot    if isPrime {        count += 1    }    print("\(n)\t\(tot)\t\(isPrime)")}print("\nNumber of primes up to 25 \t= \(count)")for n in 26..100000 {    var tot = totient(n)    if tot == n - 1 {        count += 1    }    if n == 100 || n == 1000 || n % 10000 == 0 {        print("Number of primes up to \(n) \t= \(count)")    }}`
Output:
```n       phi     prime
1       1       false
2       1       true
3       2       true
4       2       false
5       4       true
6       2       false
7       6       true
8       4       false
9       6       false
10      4       false
11      10      true
12      4       false
13      12      true
14      6       false
15      8       false
16      8       false
17      16      true
18      6       false
19      18      true
20      8       false
21      12      false
22      10      false
23      22      true
24      8       false
25      20      false

Number of primes up to 25       = 9
Number of primes up to 100      = 25
Number of primes up to 1000     = 168
Number of primes up to 10000    = 1229
Number of primes up to 20000    = 2262
Number of primes up to 30000    = 3245
Number of primes up to 40000    = 4203
Number of primes up to 50000    = 5133
Number of primes up to 60000    = 6057
Number of primes up to 70000    = 6935
Number of primes up to 80000    = 7837
Number of primes up to 90000    = 8713
Number of primes up to 100000   = 9592```

## Factor

`USING: combinators formatting io kernel math math.primes.factorsmath.ranges sequences ;IN: rosetta-code.totient-function : Φ ( n -- m )    {        { [ dup 1 < ] [ drop 0 ] }        { [ dup 1 = ] [ drop 1 ] }        [            dup unique-factors            [ 1 [ 1 - * ] reduce ] [ product ] bi / *        ]    } cond ; : show-info ( n -- )    [ Φ ] [ swap 2dup - 1 = ] bi ", prime" "" ?    "Φ(%2d) = %2d%s\n" printf ; : totient-demo ( -- )    25 [1,b] [ show-info ] each nl 0 100,000 [1,b] [        [ dup Φ - 1 = [ 1 + ] when ]        [ dup { 100 1,000 10,000 100,000 } member? ] bi        [ dupd "%4d primes <= %d\n" printf ] [ drop ] if    ] each drop ; MAIN: totient-demo`
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

25 primes <= 100
168 primes <= 1000
1229 primes <= 10000
9592 primes <= 100000
```

## FreeBASIC

Translation of: Pascal
` #define esPar(n) (((n) And 1) = 0)#define esImpar(n)  (esPar(n) = 0) Function Totient(n As Integer) As Integer    'delta son números no divisibles por 2,3,5    Dim delta(7) As Integer = {6,4,2,4,2,4,6,2}    Dim As Integer i, quot, idx, result    ' div mod por constante es rápido.    'i = 2    result = n    If (2*2 <= n) Then        If Not(esImpar(n)) Then            ' eliminar números con factor 2,4,8,16,...            While Not(esImpar(n))                n = n \ 2            Wend            'eliminar los múltiplos de 2            result -= result \ 2        End If    End If    'i = 3    If (3*3 <= n) And (n Mod 3 = 0) Then        Do            quot = n \ 3            If n <> quot*3 Then                Exit Do            Else                n = quot            End If        Loop Until false        result -= result \ 3    End If    'i = 5    If (5*5 <= n) And (n Mod 5 = 0) Then        Do            quot = n \ 5            If n <> quot*5 Then                Exit Do            Else                n = quot            End If        Loop Until false        result -= result \ 5    End If    i = 7    idx = 1    'i = 7,11,13,17,19,23,29,...,49 ..    While i*i <= n        quot = n \ i        If n = quot*i Then            Do                If n <> quot*i Then                    Exit Do                Else                    n = quot                End If                quot = n \ i            Loop Until false            result -= result \ i        End If        i = i + delta(idx)        idx = (idx+1) And 7    Wend    If n > 1 Then result -= result \ n    Totient = resultEnd Function Sub ContandoPrimos(n As Integer)    Dim As Integer i, cnt = 0    For i = 1 To n        If Totient(i) = (i-1) Then cnt += 1    Next i    Print Using " #######      ######"; i-1; cntEnd Sub Function esPrimo(n As Ulongint) As String    esPrimo = "False"    If n = 1 then Return "False"    If (n=2) Or (n=3) Then Return "True"    If n Mod 2=0 Then Exit Function    If n Mod 3=0 Then Exit Function    Dim As Ulongint limite = Sqr(N)+1    For i As Ulongint = 6 To limite Step 6        If N Mod (i-1)=0 Then Exit Function        If N Mod (i+1)=0 Then Exit Function    Next i    Return "True"End Function  Sub display(n As Integer)    Dim As Integer idx, phi    If n = 0 Then Exit Sub    Print "  n  phi(n)   esPrimo"     For idx = 1 To n        phi = Totient(idx)        Print Using "###   ###      \   \"; idx; phi; esPrimo(idx)    Next idxEnd Sub Dim l As Integerdisplay(25) Print Chr(10) & "   Limite  Son primos"ContandoPrimos(25)l = 100Do    ContandoPrimos(l)    l = l*10Loop Until l > 1000000End`
Output:
```  n  phi(n)   esPrimo
1     1      False
2     1      True
3     2      True
4     2      False
5     4      True
6     2      False
7     6      True
8     4      False
9     6      False
10     4      False
11    10      True
12     4      False
13    12      True
14     6      False
15     8      False
16     8      False
17    16      True
18     6      False
19    18      True
20     8      False
21    12      False
22    10      False
23    22      True
24     8      False
25    20      False

Limite  Son primos
25           9
100          25
1000         168
10000        1229
100000        9592
1000000       78498
```

## Fōrmulæ

Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.

Programs in Fōrmulæ are created/edited online in its website, However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used.

## Go

Results for the larger values of n are very slow to emerge.

`package main import "fmt" func gcd(n, k int) int {    if n < k || k < 1 {        panic("Need n >= k and k >= 1")    }     s := 1    for n&1 == 0 && k&1 == 0 {        n >>= 1        k >>= 1        s <<= 1    }     t := n    if n&1 != 0 {        t = -k    }    for t != 0 {        for t&1 == 0 {            t >>= 1        }        if t > 0 {            n = t        } else {            k = -t        }        t = n - k    }    return n * s} func totient(n int) int {    tot := 0    for k := 1; k <= n; k++ {        if gcd(n, k) == 1 {            tot++        }    }    return tot} func main() {    fmt.Println(" n  phi   prime")    fmt.Println("---------------")    count := 0    for n := 1; n <= 25; n++ {        tot := totient(n)        isPrime := n-1 == tot        if isPrime {            count++        }        fmt.Printf("%2d   %2d   %t\n", n, tot, isPrime)    }    fmt.Println("\nNumber of primes up to 25     =", count)    for n := 26; n <= 100000; n++ {        tot := totient(n)        if tot == n-1 {            count++        }        if n == 100 || n == 1000 || n%10000 == 0 {            fmt.Printf("\nNumber of primes up to %-6d = %d\n", n, count)        }    }}`
Output:
``` n  phi   prime
---------------
1    1   false
2    1   true
3    2   true
4    2   false
5    4   true
6    2   false
7    6   true
8    4   false
9    6   false
10    4   false
11   10   true
12    4   false
13   12   true
14    6   false
15    8   false
16    8   false
17   16   true
18    6   false
19   18   true
20    8   false
21   12   false
22   10   false
23   22   true
24    8   false
25   20   false

Number of primes up to 25     = 9

Number of primes up to 100    = 25

Number of primes up to 1000   = 168

Number of primes up to 10000  = 1229

Number of primes up to 20000  = 2262

Number of primes up to 30000  = 3245

Number of primes up to 40000  = 4203

Number of primes up to 50000  = 5133

Number of primes up to 60000  = 6057

Number of primes up to 70000  = 6935

Number of primes up to 80000  = 7837

Number of primes up to 90000  = 8713

Number of primes up to 100000 = 9592
```

The following much quicker version (runs in less than 150 ms on my machine) uses Euler's product formula rather than repeated invocation of the gcd function to calculate the totient:

`package main import "fmt" func totient(n int) int {    tot := n    for i := 2; i*i <= n; i += 2 {        if n%i == 0 {            for n%i == 0 {                n /= i            }            tot -= tot / i        }        if i == 2 {            i = 1        }    }    if n > 1 {        tot -= tot / n    }    return tot}  func main() {    fmt.Println(" n  phi   prime")    fmt.Println("---------------")    count := 0    for n := 1; n <= 25; n++ {        tot := totient(n)        isPrime := n-1 == tot        if isPrime {            count++        }        fmt.Printf("%2d   %2d   %t\n", n, tot, isPrime)    }    fmt.Println("\nNumber of primes up to 25     =", count)    for n := 26; n <= 100000; n++ {        tot := totient(n)        if tot == n-1 {            count++        }        if n == 100 || n == 1000 || n%10000 == 0 {            fmt.Printf("\nNumber of primes up to %-6d = %d\n", n, count)        }    }    }`

The output is the same as before.

Translation of: C
`{-# LANGUAGE BangPatterns #-} import Control.Monad (when)import Data.Bool (bool) totient  :: (Integral a)  => a -> atotient n  | n == 0 = 1 -- by definition phi(0) = 1  | n < 0 = totient (-n) -- phi(-n) is taken to be equal to phi(n)  | otherwise = loop n n 2 --  where    loop !m !tot !i      | i * i > m = bool tot (tot - (tot `div` m)) (1 < m)      | m `mod` i == 0 = loop m_ tot_ i_      | otherwise = loop m tot i_      where        i_          | i == 2 = 3          | otherwise = 2 + i        m_ = nextM m        tot_ = tot - (tot `div` i)        nextM !x          | x `mod` i == 0 = nextM \$ x `div` i          | otherwise = x main :: IO ()main = do  putStrLn "n\tphi\tprime\n---------------------"  let loop !i !count        | i >= 10 ^ 6 = return ()        | otherwise = do          let i_ = succ i              tot = totient i_              isPrime = tot == pred i_              count_                | isPrime = succ count                | otherwise = count          when (25 >= i_) \$            putStrLn \$ show i_ ++ "\t" ++ show tot ++ "\t" ++ show isPrime          when            (i_ `elem`             25 :             [ 10 ^ k             | k <- [2 .. 6] ]) \$            putStrLn \$ "Number of primes up to " ++ show i_ ++ " = " ++ show count_          loop (i + 1) count_  loop 0 0`
Output:
```n       phi     prime
---------------------
1       1       False
2       1       True
3       2       True
4       2       False
5       4       True
6       2       False
7       6       True
8       4       False
9       6       False
10      4       False
11      10      True
12      4       False
13      12      True
14      6       False
15      8       False
16      8       False
17      16      True
18      6       False
19      18      True
20      8       False
21      12      False
22      10      False
23      22      True
24      8       False
25      20      False
Number of primes up to 25 = 9
Number of primes up to 100 = 25
Number of primes up to 1000 = 168
Number of primes up to 10000 = 1229
Number of primes up to 100000 = 9592
Number of primes up to 1000000 = 78498
```

## J

`   nth_prime =: p:   NB. 2 is the zeroth prime   totient =: 5&p:   primeQ =:  1&p:    NB. first row contains the integer   NB. second row             totient   NB. third                  1 iff prime   (, totient ,: primeQ) >: i. 251 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 251 1 2 2 4 2 6 4 6  4 10  4 12  6  8  8 16  6 18  8 12 10 22  8 200 1 1 0 1 0 1 0 0  0  1  0  1  0  0  0  1  0  1  0  0  0  1  0  0     NB. primes first exceeding the limits   [&.:(p:inv) 10 ^ 2 + i. 4101 1009 10007 100003    p:inv 101 1009 10007 10000325 168 1229 9592    NB. limit and prime count   (,. p:inv) 10 ^ 2 + i. 5   100    25  1000   168 10000  1229100000  9592   1e6 78498 `

## Java

Efficiently pre-compute all needed values of phi up to 10,000,000 in .344 sec.

` public class TotientFunction {     public static void main(String[] args) {        computePhi();        System.out.println("Compute and display phi for the first 25 integers.");        System.out.printf("n  Phi  IsPrime%n");        for ( int n = 1 ; n <= 25 ; n++ ) {            System.out.printf("%2d  %2d  %b%n", n, phi[n], (phi[n] == n-1));        }        for ( int i = 2 ; i < 8 ; i++ ) {            int max = (int) Math.pow(10, i);            System.out.printf("The count of the primes up to %,10d = %d%n", max, countPrimes(1, max));        }    }     private static int countPrimes(int min, int max) {        int count = 0;        for ( int i = min ; i <= max ; i++ ) {            if ( phi[i] == i-1 ) {                count++;            }        }        return count;    }     private static final int max = 10000000;    private static final int[] phi = new int[max+1];     private static final void computePhi() {        for ( int i = 1 ; i <= max ; i++ ) {            phi[i] = i;        }        for ( int i = 2 ; i <= max ; i++ ) {            if (phi[i] < i) continue;            for ( int j = i ; j <= max ; j += i ) {                phi[j] -= phi[j] / i;            }        }    } } `
Output:
```Compute and display phi for the first 25 integers.
n  Phi  IsPrime
1   1  false
2   1  true
3   2  true
4   2  false
5   4  true
6   2  false
7   6  true
8   4  false
9   6  false
10   4  false
11  10  true
12   4  false
13  12  true
14   6  false
15   8  false
16   8  false
17  16  true
18   6  false
19  18  true
20   8  false
21  12  false
22  10  false
23  22  true
24   8  false
25  20  false
The count of the primes up to        100 = 25
The count of the primes up to      1,000 = 168
The count of the primes up to     10,000 = 1229
The count of the primes up to    100,000 = 9592
The count of the primes up to  1,000,000 = 78498
The count of the primes up to 10,000,000 = 664579
```

## jq

Works with: jq
` # jq optimizes the recursive call of _gcd in the following:def gcd(a;b):  def _gcd:    if .[1] != 0 then [.[1], .[0] % .[1]] | _gcd else .[0] end;  [a,b] | _gcd ; def count(s): reduce s as \$x (0; .+1); def totient:  . as \$n  | count( range(0; .) | select( gcd(\$n; .) == 1) ); # input: determines the maximum via range(0; .)# and so may be `infinite`def primes_via_totient:  range(0; .) | select(totient == . - 1); `

`def task:  def task1(\$n):    range(1;\$n)    | totient as \$totient    | {i: ., \$totient, isprime: (\$totient == ( . - 1 ))};   task1(26); def onepass:  reduce (10000 | primes_via_totient) as \$p ({};      if \$p < 10000      then .["10^4"] += 1      | if \$p < 1000        then .["10^3"] += 1        | if \$p < 100          then .["10^2"] += 1          else . end else . end else . end) ; task, "\nCounts of primes up to the given limits:", onepass`
Output:
```{"i":1,"totient":1,"isprime":false}
{"i":2,"totient":1,"isprime":true}
{"i":3,"totient":2,"isprime":true}
{"i":4,"totient":2,"isprime":false}
{"i":5,"totient":4,"isprime":true}
{"i":6,"totient":2,"isprime":false}
{"i":7,"totient":6,"isprime":true}
{"i":8,"totient":4,"isprime":false}
{"i":9,"totient":6,"isprime":false}
{"i":10,"totient":4,"isprime":false}
{"i":11,"totient":10,"isprime":true}
{"i":12,"totient":4,"isprime":false}
{"i":13,"totient":12,"isprime":true}
{"i":14,"totient":6,"isprime":false}
{"i":15,"totient":8,"isprime":false}
{"i":16,"totient":8,"isprime":false}
{"i":17,"totient":16,"isprime":true}
{"i":18,"totient":6,"isprime":false}
{"i":19,"totient":18,"isprime":true}
{"i":20,"totient":8,"isprime":false}
{"i":21,"totient":12,"isprime":false}
{"i":22,"totient":10,"isprime":false}
{"i":23,"totient":22,"isprime":true}
{"i":24,"totient":8,"isprime":false}
{"i":25,"totient":20,"isprime":false}

Counts of primes up to the given limits:
{"10^4":1229,"10^3":168,"10^2":25}
```

## Julia

Translation of: Python
`φ(n) = sum(1 for k in 1:n if gcd(n, k) == 1) is_prime(n) = φ(n) == n - 1 function runphitests()    for n in 1:25        println(" φ(\$n) == \$(φ(n))", is_prime(n) ? ", is prime" : "")    end    count = 0    for n in 1:100_000        count += is_prime(n)        if n in [100, 1000, 10_000, 100_000]            println("Primes up to \$n: \$count")        end    endend runphitests() `
Output:
```
φ(1) == 1
φ(2) == 1, is prime
φ(3) == 2, is prime
φ(4) == 2
φ(5) == 4, is prime
φ(6) == 2
φ(7) == 6, is prime
φ(8) == 4
φ(9) == 6
φ(10) == 4
φ(11) == 10, is prime
φ(12) == 4
φ(13) == 12, is prime
φ(14) == 6
φ(15) == 8
φ(16) == 8
φ(17) == 16, is prime
φ(18) == 6
φ(19) == 18, is prime
φ(20) == 8
φ(21) == 12
φ(22) == 10
φ(23) == 22, is prime
φ(24) == 8
φ(25) == 20
Primes up to 100: 25
Primes up to 1000: 168
Primes up to 10000: 1229
Primes up to 100000: 9592

```

## Kotlin

Translation of: Go
`// Version 1.3.21 fun totient(n: Int): Int {    var tot = n    var nn = n    var i = 2    while (i * i <= nn) {        if (nn % i == 0) {            while (nn % i == 0) nn /= i            tot -= tot / i        }        if (i == 2) i = 1        i += 2    }    if (nn > 1) tot -= tot / nn    return tot} fun main() {    println(" n  phi   prime")    println("---------------")    var count = 0    for (n in 1..25) {        val tot = totient(n)        val isPrime  = n - 1 == tot        if (isPrime) count++        System.out.printf("%2d   %2d   %b\n", n, tot, isPrime)    }    println("\nNumber of primes up to 25     = \$count")    for (n in 26..100_000) {        val tot = totient(n)        if (tot == n-1) count++        if (n == 100 || n == 1000 || n % 10_000 == 0) {            System.out.printf("\nNumber of primes up to %-6d = %d\n", n, count)        }    }}`
Output:
```Same as Go example.
```

## Lua

Averages about 7 seconds under LuaJIT

`-- Return the greatest common denominator of x and yfunction gcd (x, y)  return y == 0 and math.abs(x) or gcd(y, x % y)end -- Return the totient number for nfunction totient (n)  local count = 0  for k = 1, n do    if gcd(n, k) == 1 then count = count + 1 end  end  return countend -- Determine (inefficiently) whether p is primefunction isPrime (p)  return totient(p) == p - 1end -- Output totient and primality for the first 25 integersprint("n", string.char(237), "prime")print(string.rep("-", 21))for i = 1, 25 do  print(i, totient(i), isPrime(i))end -- Count the primes up to 100, 1000 and 10000local pCount, i, limit = 0, 1for power = 2, 4 do  limit = 10 ^ power  repeat    i = i + 1    if isPrime(i) then pCount = pCount + 1 end  until i == limit  print("\nThere are " .. pCount .. " primes below " .. limit)end`
Output:
```n       φ       prime
---------------------
1       1       false
2       1       true
3       2       true
4       2       false
5       4       true
6       2       false
7       6       true
8       4       false
9       6       false
10      4       false
11      10      true
12      4       false
13      12      true
14      6       false
15      8       false
16      8       false
17      16      true
18      6       false
19      18      true
20      8       false
21      12      false
22      10      false
23      22      true
24      8       false
25      20      false

There are 25 primes below 100

There are 168 primes below 1000

There are 1229 primes below 10000```

## Mathematica / Wolfram Language

`Do[ tmp = EulerPhi[i]; If[i - 1 == tmp,  Print["\[CurlyPhi](", i, ")=", tmp, ", is prime"]  ,  Print["\[CurlyPhi](", i, ")=", tmp]  ] , {i, 25} ]Count[EulerPhi[Range[100]] - Range[100], -1]Count[EulerPhi[Range[1000]] - Range[1000], -1]Count[EulerPhi[Range[10000]] - Range[10000], -1]Count[EulerPhi[Range[100000]] - Range[100000], -1](*Alternative much faster way of findings the number primes up to a number*)(*PrimePi[100]*)(*PrimePi[1000]*)(*PrimePi[10000]*)(*PrimePi[100000]*)`
Output:
```φ(1)=1
φ(2)=1, is prime
φ(3)=2, is prime
φ(4)=2
φ(5)=4, is prime
φ(6)=2
φ(7)=6, is prime
φ(8)=4
φ(9)=6
φ(10)=4
φ(11)=10, is prime
φ(12)=4
φ(13)=12, is prime
φ(14)=6
φ(15)=8
φ(16)=8
φ(17)=16, is prime
φ(18)=6
φ(19)=18, is prime
φ(20)=8
φ(21)=12
φ(22)=10
φ(23)=22, is prime
φ(24)=8
φ(25)=20

25
168
1229
9592```

## Nim

`import strformat func totient(n: int): int =    var tot = n    var nn = n    var i = 2    while i * i <= nn:        if nn mod i == 0:            while nn mod i == 0:                nn = nn div i            dec tot, tot div i        if i == 2:            i = 1        inc i, 2    if nn > 1:        dec tot, tot div nn    tot echo " n    φ   prime"echo "---------------"var count = 0for n in 1..25:    let tot = totient(n)    let isPrime = n - 1 == tot    if isPrime:        inc count    echo fmt"{n:2}   {tot:2}   {isPrime}"echo ""echo fmt"Number of primes up to {25:>6} = {count:>4}"for n in 26..100_000:    let tot = totient(n)    if tot == n - 1:        inc count    if n == 100 or n == 1000 or n mod 10_000 == 0:        echo fmt"Number of primes up to {n:>6} = {count:>4}"`
Output:
``` n    φ   prime
---------------
1    1   false
2    1   true
3    2   true
4    2   false
5    4   true
6    2   false
7    6   true
8    4   false
9    6   false
10    4   false
11   10   true
12    4   false
13   12   true
14    6   false
15    8   false
16    8   false
17   16   true
18    6   false
19   18   true
20    8   false
21   12   false
22   10   false
23   22   true
24    8   false
25   20   false

Number of primes up to     25 =    9
Number of primes up to    100 =   25
Number of primes up to   1000 =  168
Number of primes up to  10000 = 1229
Number of primes up to  20000 = 2262
Number of primes up to  30000 = 3245
Number of primes up to  40000 = 4203
Number of primes up to  50000 = 5133
Number of primes up to  60000 = 6057
Number of primes up to  70000 = 6935
Number of primes up to  80000 = 7837
Number of primes up to  90000 = 8713
Number of primes up to 100000 = 9592
```

## Pascal

Yes, a very slow possibility to check prime

`{\$IFDEF FPC}  {\$MODE DELPHI}{\$IFEND}function gcd_mod(u, v: NativeUint): NativeUint;inline;//prerequisites  u > v and u,v > 0  var    t: NativeUInt;  begin    repeat      t := u;      u := v;      v := t mod v;    until v = 0;    gcd_mod := u;  end; function Totient(n:NativeUint):NativeUint;var  i : NativeUint;Begin  result := 1;  For i := 2 to n do    inc(result,ORD(GCD_mod(n,i)=1));end; function CheckPrimeTotient(n:NativeUint):Boolean;inline;begin  result :=  (Totient(n) = (n-1));end; procedure OutCountPrimes(n:NativeUInt);var  i,cnt :  NativeUint;begin  cnt := 0;  For i := 1 to n do    inc(cnt,Ord(CheckPrimeTotient(i)));  writeln(n:10,cnt:8);end; procedure display(n:NativeUint);var  idx,phi : NativeUint;Begin  if n = 0 then    EXIT;  writeln('number n':5,'Totient(n)':11,'isprime':8);  For idx := 1 to n do  Begin    phi := Totient(idx);    writeln(idx:4,phi:10,(phi=(idx-1)):12);  endend;var  i : NativeUint;Begin  display(25);   writeln('Limit  primecount');  i := 100;  repeat    OutCountPrimes(i);    i := i*10;  until i >100000;end.`
Output
```number n Totient(n) isprime
1         1       FALSE
2         1        TRUE
3         2        TRUE
4         2       FALSE
5         4        TRUE
6         2       FALSE
7         6        TRUE
8         4       FALSE
9         6       FALSE
10         4       FALSE
11        10        TRUE
12         4       FALSE
13        12        TRUE
14         6       FALSE
15         8       FALSE
16         8       FALSE
17        16        TRUE
18         6       FALSE
19        18        TRUE
20         8       FALSE
21        12       FALSE
22        10       FALSE
23        22        TRUE
24         8       FALSE
25        20       FALSE
Limit  primecount
100      25
1000     168
10000    1229
100000    9592

real  3m39,745s```

### alternative

changing Totient-funtion in program atop to Computing Euler's totient function on wikipedia, like GO and C.

Impressive speedup.Checking with only primes would be even faster.

`function totient(n:NativeUInt):NativeUInt;const  //delta of numbers not divisible by 2,3,5 (0_1+6->7+4->11 ..+6->29+2->3_1  delta : array[0..7] of NativeUint = (6,4,2,4,2,4,6,2);var  i, quot,idx: NativeUint;Begin  // div mod by constant is fast.  //i = 2  result := n;  if (2*2 <= n) then  Begin    IF not(ODD(n)) then    Begin      // remove numbers with factor 2,4,8,16, ...      while not(ODD(n)) do        n := n DIV 2;      //remove count of multiples of 2      dec(result,result DIV 2);    end;  end;  //i = 3  If (3*3 <= n) AND (n mod 3 = 0) then  Begin    repeat      quot := n DIV 3;      IF n <> quot*3 then        BREAK      else        n := quot;    until false;    dec(result,result DIV 3);  end;  //i = 5  If (5*5 <= n) AND (n mod 5 = 0) then  Begin    repeat      quot := n DIV 5;      IF n <> quot*5 then        BREAK      else        n := quot;    until false;    dec(result,result DIV 5);  end;  i := 7;  idx := 1;  //i = 7,11,13,17,19,23,29, ...49 ..  while i*i <= n do  Begin    quot := n DIV i;    if n = quot*i then    Begin      repeat        IF n <> quot*i then          BREAK        else          n := quot;        quot := n DIV i;      until false;      dec(result,result DIV i);    end;    i := i + delta[idx];    idx := (idx+1) AND 7;  end;  if n> 1 then    dec(result,result div n);end;`
Output
```number n Totient(n) isprime
1         1       FALSE
2         1        TRUE
3         2        TRUE
4         2       FALSE
5         4        TRUE
6         2       FALSE
7         6        TRUE
8         4       FALSE
9         6       FALSE
10         4       FALSE
11        10        TRUE
12         4       FALSE
13        12        TRUE
14         6       FALSE
15         8       FALSE
16         8       FALSE
17        16        TRUE
18         6       FALSE
19        18        TRUE
20         8       FALSE
21        12       FALSE
22        10       FALSE
23        22        TRUE
24         8       FALSE
25        20       FALSE
Limit  primecount
100      25
1000     168
10000    1229
100000    9592
1000000   78498
10000000  664579

real	0m7,369s```

## Perl

#### Direct calculation of 𝜑

Translation of: Raku
`use utf8;binmode STDOUT, ":utf8"; sub gcd {  my (\$u, \$v) = @_;  while (\$v) {    (\$u, \$v) = (\$v, \$u % \$v);  }  return abs(\$u);} push @𝜑, 0;for \$t (1..10000) {    push @𝜑, scalar grep { 1 == gcd(\$_,\$t) } 1..\$t;} printf "𝜑(%2d) = %3d%s\n", \$_, \$𝜑[\$_], \$_ - \$𝜑[\$_] - 1 ? '' : ' Prime' for 1 .. 25;print "\n"; for \$limit (100, 1000, 10000) {    printf "Count of primes <= \$limit: %d\n", scalar grep {\$_ == \$𝜑[\$_] + 1} 0..\$limit;} `
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```

#### Using 'ntheory' library

Much faster. Output is the same as above.

Library: ntheory
`use utf8;binmode STDOUT, ":utf8"; use ntheory qw(euler_phi); my @𝜑 = euler_phi(0,10000);  # Returns list of all values in range printf "𝜑(%2d) = %3d%s\n", \$_, \$𝜑[\$_], \$_ - \$𝜑[\$_] - 1 ? '' : ' Prime' for 1 .. 25;print "\n"; for \$limit (100, 1000, 10000) {    printf "Count of primes <= \$limit: %d\n", scalar grep {\$_ == \$𝜑[\$_] + 1} 0..\$limit;}`

## Phix

Translation of: Go
```function totient(integer n)
integer tot = n, i = 2
while i*i<=n do
if mod(n,i)=0 then
while true do
n /= i
if mod(n,i)!=0 then exit end if
end while
tot -= tot/i
end if
i += iff(i=2?1:2)
end while
if n>1 then
tot -= tot/n
end if
end function

printf(1," n  phi   prime\n")
printf(1," --------------\n")
integer count = 0
for n=1 to 25 do
integer tot = totient(n),
prime = (n-1=tot)
count += prime
string isp = iff(prime?"true":"false")
printf(1,"%2d   %2d   %s\n",{n,tot,isp})
end for
printf(1,"\nNumber of primes up to 25     = %d\n",count)
for n=26 to 100000 do
count += (totient(n)=n-1)
if find(n,{100,1000,10000,100000}) then
printf(1,"Number of primes up to %-6d = %d\n",{n,count})
end if
end for
```
Output:
``` n  phi   prime
--------------
1    1   false
2    1   true
3    2   true
4    2   false
5    4   true
6    2   false
7    6   true
8    4   false
9    6   false
10    4   false
11   10   true
12    4   false
13   12   true
14    6   false
15    8   false
16    8   false
17   16   true
18    6   false
19   18   true
20    8   false
21   12   false
22   10   false
23   22   true
24    8   false
25   20   false

Number of primes up to 25     = 9
Number of primes up to 100    = 25
Number of primes up to 1000   = 168
Number of primes up to 10000  = 1229
Number of primes up to 100000 = 9592
```

## PicoLisp

`(gc 32)(de gcd (A B)   (until (=0 B)      (let M (% A B)         (setq A B B M) ) )   (abs A) )(de totient (N)   (let C 0      (for I N         (and (=1 (gcd N I)) (inc 'C)) )      (cons C (= C (dec N))) ) )(de p? (N)   (let C 0      (for A N         (and            (cdr (totient A))            (inc 'C) ) )      C ) )(let Fmt (3 7 10)   (tab Fmt "N" "Phi" "Prime?")   (tab Fmt "-" "---" "------")   (for N 25      (tab Fmt         N         (car (setq @ (totient N)))         (cdr @) ) ) )(println   (mapcar p? (25 100 1000 10000 100000)) )`
Output:
```
N    Phi    Prime?
-    ---    ------
1      1
2      1         T
3      2         T
4      2
5      4         T
6      2
7      6         T
8      4
9      6
10      4
11     10         T
12      4
13     12         T
14      6
15      8
16      8
17     16         T
18      6
19     18         T
20      8
21     12
22     10
23     22         T
24      8
25     20
(9 25 168 1229 9592)```

## Python

`from math import gcd def  φ(n):    return sum(1 for k in range(1, n + 1) if gcd(n, k) == 1) if __name__ == '__main__':    def is_prime(n):        return φ(n) == n - 1     for n in range(1, 26):        print(f" φ({n}) == {φ(n)}{', is prime' if is_prime(n)  else ''}")    count = 0    for n in range(1, 10_000 + 1):        count += is_prime(n)        if n in {100, 1000, 10_000}:            print(f"Primes up to {n}: {count}")`
Output:
``` φ(1) == 1
φ(2) == 1, is prime
φ(3) == 2, is prime
φ(4) == 2
φ(5) == 4, is prime
φ(6) == 2
φ(7) == 6, is prime
φ(8) == 4
φ(9) == 6
φ(10) == 4
φ(11) == 10, is prime
φ(12) == 4
φ(13) == 12, is prime
φ(14) == 6
φ(15) == 8
φ(16) == 8
φ(17) == 16, is prime
φ(18) == 6
φ(19) == 18, is prime
φ(20) == 8
φ(21) == 12
φ(22) == 10
φ(23) == 22, is prime
φ(24) == 8
φ(25) == 20
Primes up to 100: 25
Primes up to 1000: 168
Primes up to 10000: 1229```

## Quackery

`  [ [ dup while      tuck mod again ]    drop abs ]              is gcd        ( n n --> n )    [ 0 swap dup times       [ i over gcd         1 = rot + swap ]       drop ]                is totient    (   n --> n )   [ 0 temp put    times      [ i dup 1+ totient        = temp tally ]     temp take ]            is primecount (   n --> n )   25 times     [ say "The totient of "       i^ 1+ dup echo       say " is "       dup totient dup echo       say ", so it is "       1+ != if say "not "       say "prime." cr ]   cr  ' [ 100 1000 10000 100000 ]   witheach     [ say "There are "      dup primecount echo       say " primes up to " echo      say "." cr ]`

((Out}}

```The totient of 1 is 1, so it is not prime.
The totient of 2 is 1, so it is prime.
The totient of 3 is 2, so it is prime.
The totient of 4 is 2, so it is not prime.
The totient of 5 is 4, so it is prime.
The totient of 6 is 2, so it is not prime.
The totient of 7 is 6, so it is prime.
The totient of 8 is 4, so it is not prime.
The totient of 9 is 6, so it is not prime.
The totient of 10 is 4, so it is not prime.
The totient of 11 is 10, so it is prime.
The totient of 12 is 4, so it is not prime.
The totient of 13 is 12, so it is prime.
The totient of 14 is 6, so it is not prime.
The totient of 15 is 8, so it is not prime.
The totient of 16 is 8, so it is not prime.
The totient of 17 is 16, so it is prime.
The totient of 18 is 6, so it is not prime.
The totient of 19 is 18, so it is prime.
The totient of 20 is 8, so it is not prime.
The totient of 21 is 12, so it is not prime.
The totient of 22 is 10, so it is not prime.
The totient of 23 is 22, so it is prime.
The totient of 24 is 8, so it is not prime.
The totient of 25 is 20, so it is not prime.

There are 25 primes up to 100.
There are 168 primes up to 1000.
There are 1229 primes up to 10000.
There are 9592 primes up to 100000.```

## Racket

`#lang racket (require math/number-theory) (define (prime*? n) (= (totient n) (sub1 n))) (for ([n (in-range 1 26)])  (printf "φ(~a) = ~a~a~a\n"          n          (totient n)          (if (prime*? n) " is prime" "")          (if (prime? n) " (confirmed)" ""))) (for/fold ([count 0] #:result (void)) ([n (in-range 1 10001)])   (define new-count (if (prime*? n) (add1 count) count))   (when (member n '(100 1000 10000))     (printf "Primes up to ~a: ~a\n" n new-count))   new-count)`
Output:
```φ(1) = 1
φ(2) = 1 is prime (confirmed)
φ(3) = 2 is prime (confirmed)
φ(4) = 2
φ(5) = 4 is prime (confirmed)
φ(6) = 2
φ(7) = 6 is prime (confirmed)
φ(8) = 4
φ(9) = 6
φ(10) = 4
φ(11) = 10 is prime (confirmed)
φ(12) = 4
φ(13) = 12 is prime (confirmed)
φ(14) = 6
φ(15) = 8
φ(16) = 8
φ(17) = 16 is prime (confirmed)
φ(18) = 6
φ(19) = 18 is prime (confirmed)
φ(20) = 8
φ(21) = 12
φ(22) = 10
φ(23) = 22 is prime (confirmed)
φ(24) = 8
φ(25) = 20
Primes up to 100: 25
Primes up to 1000: 168
Primes up to 10000: 1229
```

## Raku

(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```

## REXX

### idiomatic

`/*REXX program calculates the totient numbers for a range of numbers, and count primes. */parse arg N .                                    /*obtain optional argument from the CL.*/if N==''  |  N==","  then N= 25                  /*Not specified?  Then use the default.*/tell= N>0                                        /*N positive>?  Then display them all. */N= abs(N)                                        /*use the absolute value of N for loop.*/w= length(N)                                     /*W:  is used in aligning the output.  */primes= 0                                        /*the number of primes found  (so far).*/                                                 /*if N was negative, only count primes.*/    do j=1  for  N;              T= phi(j)       /*obtain totient number for a number.  */    prime= word('(prime)', 1 +  (T \== j-1 ) )   /*determine if  J  is a prime number.  */    if prime\==''  then primes= primes + 1       /*if a prime, then bump the prime count*/    if tell  then say 'totient number for '  right(j, w)  " ──► "  right(T, w)  ' '  prime    end   /*j*/saysay right(primes, w)      ' primes detected for numbers up to and including '        Nexit 0                                           /*stick a fork in it,  we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/gcd: parse arg x,y;   do until y==0;     parse value   x//y  y    with    y  x                      end   /*until*/;                                            return x/*──────────────────────────────────────────────────────────────────────────────────────*/phi: procedure; parse arg z;             if z==1  then return 1     #= 1                      do m=2  for z-2;   if gcd(m, z)==1  then #= # + 1                      end   /*m*/;                                                return #`
output   when using the default input of:     25
```totient number for   1  ──►   1
totient number for   2  ──►   1   (prime)
totient number for   3  ──►   2   (prime)
totient number for   4  ──►   2
totient number for   5  ──►   4   (prime)
totient number for   6  ──►   2
totient number for   7  ──►   6   (prime)
totient number for   8  ──►   4
totient number for   9  ──►   6
totient number for  10  ──►   4
totient number for  11  ──►  10   (prime)
totient number for  12  ──►   4
totient number for  13  ──►  12   (prime)
totient number for  14  ──►   6
totient number for  15  ──►   8
totient number for  16  ──►   8
totient number for  17  ──►  16   (prime)
totient number for  18  ──►   6
totient number for  19  ──►  18   (prime)
totient number for  20  ──►   8
totient number for  21  ──►  12
totient number for  22  ──►  10
totient number for  23  ──►  22   (prime)
totient number for  24  ──►   8
totient number for  25  ──►  20

9  primes detected for numbers up to and including  25
```
output   when using the input of:     -100
``` 25  primes detected for numbers up to and including  100
```
output   when using the input of:     -1000
``` 168  primes detected for numbers up to and including  1000
```
output   when using the input of:     -10000
``` 1229  primes detected for numbers up to and including  10000
```
output   when using the input of:     -1000000
``` 9592 primes detected for numbers up to and including  100000
```

### optimized

This REXX version moved the   gcd   function in-line.
It is about   7%   faster than the 1st version.

`/*REXX program calculates the totient numbers for a range of numbers, and count primes. */parse arg N .                                    /*obtain optional argument from the CL.*/if N==''  |  N==","  then N= 25                  /*Not specified?  Then use the default.*/tell= N>0                                        /*N positive>?  Then display them all. */N= abs(N)                                        /*use the absolute value of N for loop.*/w= length(N)                                     /*W:  is used in aligning the output.  */primes= 0                                        /*the number of primes found  (so far).*/                                                 /*if N was negative, only count primes.*/    do j=1  for  N;              T= phi(j)       /*obtain totient number for a number.  */    prime= word('(prime)', 1 +  (T \== j-1 ) )   /*determine if  J  is a prime number.  */    if prime\==''  then primes= primes + 1       /*if a prime, then bump the prime count*/    if tell  then say 'totient number for '  right(j, w)  " ──► "  right(T, w)  ' '  prime    end   /*j*/saysay right(primes, w)      ' primes detected for numbers up to and including '        Nexit 0                                           /*stick a fork in it,  we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/phi: procedure; parse arg z;                       if z==1  then return 1     #= 1                            do m=2  for z-2;       parse value     m   z    with    x  y                                do until y==0;     parse value   x//y  y    with    y  x                                end   /*until*/                            if x==1  then #= # + 1                            end       /*m*/     return #`
output   is identical to the 1st REXX version.

## Ruby

` require "prime" def 𝜑(n)  n.prime_division.inject(1) {|res, (pr, exp)| res *= (pr-1) * pr**(exp-1) } end 1.upto 25 do |n|  tot = 𝜑(n)  puts "#{n}\t #{tot}\t #{"prime" if n-tot==1}"end [100, 1_000, 10_000, 100_000].each do |u|  puts "Number of primes up to #{u}: #{(1..u).count{|n| n-𝜑(n) == 1} }"end `
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
Number of primes up to 100: 25
Number of primes up to 1000: 168
Number of primes up to 10000: 1229
Number of primes up to 100000: 9592
```

## Rust

`use num::integer::gcd; fn main() {    // Compute the totient of the first 25 natural integers    println!("N\t phi(n)\t Prime");    for n in 1..26 {        let phi_n = phi(n);        println!("{}\t {}\t {:?}", n, phi_n, phi_n == n - 1);    }     // Compute the number of prime numbers for various steps    [1, 100, 1000, 10000, 100000]        .windows(2)        .scan(0, |acc, tuple| {            *acc += (tuple[0]..=tuple[1]).filter(is_prime).count();            Some((tuple[1], *acc))        })        .for_each(|x| println!("Until {}: {} prime numbers", x.0, x.1));} fn is_prime(n: &usize) -> bool {    phi(*n) == *n - 1} fn phi(n: usize) -> usize {    (1..=n).filter(|&x| gcd(n, x) == 1).count()}`

Output is:

```N	 phi(n)	 Prime
1	 1	 false
2	 1	 true
3	 2	 true
4	 2	 false
5	 4	 true
6	 2	 false
7	 6	 true
8	 4	 false
9	 6	 false
10	 4	 false
11	 10	 true
12	 4	 false
13	 12	 true
14	 6	 false
15	 8	 false
16	 8	 false
17	 16	 true
18	 6	 false
19	 18	 true
20	 8	 false
21	 12	 false
22	 10	 false
23	 22	 true
24	 8	 false
25	 20	 false
Until 100: 25 prime numbers
Until 1000: 168 prime numbers
Until 10000: 1229 prime numbers
Until 100000: 9592 prime numbers
```

## Scala

The most concise way to write the totient function in Scala is using a naive lazy list:

`@tailrecdef gcd(a: Int, b: Int): Int = if(b == 0) a else gcd(b, a%b)def totientLaz(num: Int): Int = LazyList.range(2, num).count(gcd(num, _) == 1) + 1`

The above approach, while concise, is not very performant. It must check the GCD with every number between 2 and num, giving it an O(n*log(n)) time complexity. A better solution is to use the product definition of the totient, repeatedly extracting prime factors from num:

`def totientPrd(num: Int): Int = {  @tailrec  def dTrec(f: Int, n: Int): Int = if(n%f == 0) dTrec(f, n/f) else n   @tailrec  def tTrec(ac: Int, i: Int, n: Int): Int = if(n != 1){    if(n%i == 0) tTrec(ac*(i - 1)/i, i + 1, dTrec(i, n))    else tTrec(ac, i + 1, n)  }else{    ac  }   tTrec(num, 2, num)}`

This version is significantly faster, but the introduction of multiple recursive methods makes it far less concise. We can, however, embed the recursion into a lazy list to obtain a function as fast as the second example yet almost as concise as the first, at the cost of some readability:

`@tailrecdef scrub(f: Long, num: Long): Long = if(num%f == 0) scrub(f, num/f) else numdef totientLazPrd(num: Long): Long = LazyList.iterate((num, 2: Long, num)){case (ac, i, n) => if(n%i == 0) (ac*(i - 1)/i, i + 1, scrub(i, n)) else (ac, i + 1, n)}.find(_._3 == 1).get._1`

To generate the output up to 100000, Longs are necessary.

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

Prime Count <= N...
100: 25
1000: 168
10000: 1229
100000: 9592```

## Shale

```#!/usr/local/bin/shale

primes library

init dup var {
pl sieve type primes::()
100000 0 pl generate primes::()
} =

go dup var {
i var
c0 var
c1 var
c2 var
c3 var
p var

" N  Phi  Is prime" println
i 1 =
{ i 25 <= } {
i pl isprime primes::() { "True" } { "False" } if i pl phi primes::() i "%2d  %3d  %s\n" printf
i++
} while

c0 0 =
c1 0 =
c2 0 =
c3 0 =
i 0 =
{ i count pl:: < } {
p i pl get primes::() =
p 100 < { c0++ } ifthen
p 1000 < { c1++ } ifthen
p 10000 < { c2 ++ } ifthen
p 100000 < { c3 ++ } ifthen
i++
} while

"" println
"  Limit  Count" println
c0 "    100  %5d\n" printf
c1 "  1,000  %5d\n" printf
c2 " 10,000  %5d\n" printf
c3 "100,000  %5d\n" printf
} =

init()
go()
```
Output:
``` N  Phi  Is prime
1    1  False
2    1  True
3    2  True
4    2  False
5    4  True
6    2  False
7    6  True
8    4  False
9    6  False
10    4  False
11   10  True
12    4  False
13   12  True
14    6  False
15    8  False
16    8  False
17   16  True
18    6  False
19   18  True
20    8  False
21   12  False
22   10  False
23   22  True
24    8  False
25   20  False

Limit  Count
100     25
1,000    168
10,000   1229
100,000   9592
```

## Sidef

The Euler totient function is built-in as Number.euler_phi(), but we can easily re-implement it using its multiplicative property: phi(p^k) = (p-1)*p^(k-1).

`func 𝜑(n) {    n.factor_exp.prod {|p|        (p[0]-1) * p[0]**(p[1]-1)    }}`
`for n in (1..25) {    var totient = 𝜑(n)    printf("𝜑(%2s) = %3s%s\n", n, totient, totient==(n-1) ? ' - prime' : '')}`
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
```
`[100, 1_000, 10_000, 100_000].each {|limit|    var pi = (1..limit -> count_by {|n| 𝜑(n) == (n-1) })    say "Number of primes <= #{limit}: #{pi}"}`
Output:
```Number of primes <= 100: 25
Number of primes <= 1000: 168
Number of primes <= 10000: 1229
Number of primes <= 100000: 9592
```

## Tiny BASIC

1 indicates prime, 0 indicates not prime.

`     REM PRINT THE DATA FOR N=1 TO 25     LET N = 0  10 LET N = N + 1     IF N = 26 THEN GOTO 100     GOSUB 1000     IF T = N - 1 THEN LET P = 1     IF T <> N - 1 THEN LET P = 0     PRINT N," ", T," ",P     GOTO 10 100 REM COUNT PRIMES BELOW 10000     LET C = 0     LET N = 2 110 GOSUB 1000     IF T = N - 1 THEN LET C = C + 1     IF N = 100 THEN PRINT "There are ", C, " primes below 100."     IF N = 1000 THEN PRINT "There are ", C, " primes below 1000."     IF N = 10000 THEN PRINT "There are ", C, " primes below 10000."     LET N = N + 1     IF N < 10001 THEN GOTO 110     END1000 REM TOTIENT FUNCTION OF INTEGER N     LET M = 1     LET T = 01010 IF M > N THEN RETURN     LET A = N     LET B = M    REM NEED TO RENAME THESE SO THEY ARE PRESERVED     GOSUB 2000     IF G = 1 THEN LET T = T + 1     LET M = M + 1     GOTO 10102000 REM GCD OF INTEGERS A, B2010 IF A>B THEN GOTO 2020     LET B = B - A     IF A=0 THEN LET G = B     IF A=0 THEN RETURN2020 LET S = A     LET A = B     LET B = S     GOTO 2010`
Output:
```1 1 0
2 1 1
3 2 1
4 2 0
5 4 1
6 2 0
7 6 1
8 4 0
9 6 0
10 4 0
11 10 1
12 4 0
13 12 1
14 6 0
15 8 0
16 8 0
17 16 1
18 6 0
19 18 1
20 8 0
21 12 0
22 10 0
23 22 1
24 8 0
25 20 0
There are 25 primes below 100.
There are 168 primes below 1000.

There are 1229 primes below 10000.```

## VBA

Translation of: Phix
`Private Function totient(ByVal n As Long) As Long    Dim tot As Long: tot = n    Dim i As Long: i = 2    Do While i * i <= n        If n Mod i = 0 Then            Do While True                n = n \ i                If n Mod i <> 0 Then Exit Do            Loop            tot = tot - tot \ i        End If        i = i + IIf(i = 2, 1, 2)    Loop    If n > 1 Then        tot = tot - tot \ n    End If    totient = totEnd Function Public Sub main()    Debug.Print " n  phi   prime"    Debug.Print " --------------"    Dim count As Long    Dim tot As Integer, n As Long    For n = 1 To 25        tot = totient(n)        prime = (n - 1 = tot)        count = count - prime        Debug.Print Format(n, "@@"); Format(tot, "@@@@@"); Format(prime, "@@@@@@@@")    Next n    Debug.Print    Debug.Print "Number of primes up to 25     = "; Format(count, "@@@@")    For n = 26 To 100000        count = count - (totient(n) = n - 1)        Select Case n            Case 100, 1000, 10000, 100000                Debug.Print "Number of primes up to"; n; String\$(6 - Len(CStr(n)), " "); "="; Format(count, "@@@@@")            Case Else        End Select    Next nEnd Sub`
Output:
``` n  phi   prime
--------------
1    1   False
2    1    True
3    2    True
4    2   False
5    4    True
6    2   False
7    6    True
8    4   False
9    6   False
10    4   False
11   10    True
12    4   False
13   12    True
14    6   False
15    8   False
16    8   False
17   16    True
18    6   False
19   18    True
20    8   False
21   12   False
22   10   False
23   22    True
24    8   False
25   20   False

Number of primes up to 25     =    9
Number of primes up to 100    =   25
Number of primes up to 1000   =  168
Number of primes up to 10000  = 1229
Number of primes up to 100000 = 9592```

## Visual Basic .NET

Translation of: C#
`Imports System.Linq.Enumerable Module Module1     Sub Main()        For i = 1 To 25            Dim t = Totient(i)            Console.WriteLine("{0}{1}{2}{3}", i, vbTab, t, If(t = i - 1, vbTab & "prime", ""))        Next        Console.WriteLine()         Dim j = 100        While j <= 100000            Console.WriteLine(\$"{Range(1, j).Count(Function(x) Totient(x) + 1 = x):n0} primes below {j:n0}")            j *= 10        End While    End Sub     Function Totient(n As Integer) As Integer        If n < 3 Then            Return 1        End If        If n = 3 Then            Return 2        End If         Dim tot = n         If (n And 1) = 0 Then            tot >>= 1            Do                n >>= 1            Loop While (n And 1) = 0        End If         Dim i = 3        While i * i <= n            If n Mod i = 0 Then                tot -= tot \ i                Do                    n \= i                Loop While (n Mod i) = 0            End If            i += 2        End While         If n > 1 Then            tot -= tot \ n        End If         Return tot    End Function End Module`
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

25 primes below 100
168 primes below 1,000
1,229 primes below 10,000
9,592 primes below 100,000```

## Wren

Translation of: Go
Library: Wren-fmt
`import "/fmt" for Fmt var totient = Fn.new { |n|    var tot = n    var i = 2    while (i*i <= n) {        if (n%i == 0) {            while(n%i == 0) n = (n/i).floor            tot = tot - (tot/i).floor        }        if (i == 2) i = 1        i = i + 2    }    if (n > 1) tot = tot - (tot/n).floor    return tot} System.print(" n  phi   prime")System.print("---------------")var count = 0for (n in 1..25) {    var tot = totient.call(n)    var isPrime = (n - 1) == tot    if (isPrime) count = count + 1    System.print("%(Fmt.d(2, n))   %(Fmt.d(2, tot))   %(isPrime)")}System.print("\nNumber of primes up to 25     = %(count)")for (n in 26..100000) {    var tot = totient.call(n)    if (tot == n - 1) count = count + 1    if (n == 100 || n == 1000 || n%10000 == 0) {        System.print("\nNumber of primes up to %(Fmt.d(-6, n)) = %(count)")    }}`
Output:
``` n  phi   prime
---------------
1    1   false
2    1   true
3    2   true
4    2   false
5    4   true
6    2   false
7    6   true
8    4   false
9    6   false
10    4   false
11   10   true
12    4   false
13   12   true
14    6   false
15    8   false
16    8   false
17   16   true
18    6   false
19   18   true
20    8   false
21   12   false
22   10   false
23   22   true
24    8   false
25   20   false

Number of primes up to 25     = 9

Number of primes up to 100    = 25

Number of primes up to 1000   = 168

Number of primes up to 10000  = 1229

Number of primes up to 20000  = 2262

Number of primes up to 30000  = 3245

Number of primes up to 40000  = 4203

Number of primes up to 50000  = 5133

Number of primes up to 60000  = 6057

Number of primes up to 70000  = 6935

Number of primes up to 80000  = 7837

Number of primes up to 90000  = 8713

Number of primes up to 100000 = 9592
```

## zkl

`fcn totient(n){ [1..n].reduce('wrap(p,k){ p + (n.gcd(k)==1) }) }fcn isPrime(n){ totient(n)==(n - 1) }`
`foreach n in ([1..25]){   println("\u03c6(%2d) ==%3d %s"      .fmt(n,totient(n),isPrime(n) and "is prime" or ""));}`
Output:
```φ( 1) ==  1
φ( 2) ==  1 is prime
φ( 3) ==  2 is prime
φ( 4) ==  2
φ( 5) ==  4 is prime
φ( 6) ==  2
φ( 7) ==  6 is prime
φ( 8) ==  4
φ( 9) ==  6
φ(10) ==  4
φ(11) == 10 is prime
φ(12) ==  4
φ(13) == 12 is prime
φ(14) ==  6
φ(15) ==  8
φ(16) ==  8
φ(17) == 16 is prime
φ(18) ==  6
φ(19) == 18 is prime
φ(20) ==  8
φ(21) == 12
φ(22) == 10
φ(23) == 22 is prime
φ(24) ==  8
φ(25) == 20
```
`count:=0;foreach n in ([1..10_000]){	// yes, this is sloooow   count+=isPrime(n);   if(n==100 or n==1000 or n==10_000)      println("Primes <= %,6d : %,5d".fmt(n,count));}`
Output:
```Primes <=    100 :    25
Primes <=  1,000 :   168
Primes <= 10,000 : 1,229
```