# 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

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

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

## 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.

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

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

## 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: Perl 6
`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;}`

## Perl 6

Works with: Rakudo version 2018.11

This is an incredibly inefficient way of finding prime numbers.

`my \π = 0, |(1..*).hyper(:8degree).map: -> \$t { +(^\$t).grep: * gcd \$t == 1 }; printf "π(%2d) = %3d %s\n", \$_, π[\$_], \$_ - π[\$_] - 1 ?? '' !! 'Prime' for 1 .. 25; (100, 1000, 10000).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```

## 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    return totend function printf(1," n  phi   prime\n")printf(1," --------------\n")integer count = 0for 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 forprintf(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 ifend 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```

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

## REXX

`/*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 to aligning the output.  */primes= 0                                        /*the number of primes found  (so far).*/                                                 /*if N was negative, only count primes.*/    do j=1  for  N;     tn= phi(j)               /*obtain totient number for a number.  */    prime= word('(prime)', 1 +  (tn \== 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(tn, w) ' ' prime    end   /*j*/saysay right(primes, w)    ' primes detected for numbers up to and including '    Nexit                                             /*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;  #= z==1                      do m=1  for z-1;  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
```

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

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

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

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