⚠️ Warning: This is a draft ⚠️

This means it might contain formatting issues, incorrect code, conceptual problems, or other severe issues.

If you want to help to improve and eventually enable this page, please fork RosettaGit's repository and open a merge request on GitHub.

The '''totient''' function is also known as: ::* Euler's totient function ::* Euler's phi totient function ::* phi totient function ::* Φ function (uppercase Greek phi) ::* φ function (lowercase Greek phi)

;Definitions (as per number theory): The totient function: ::* counts the integers up to a given positive integer '''n''' that are relatively prime to '''n''' ::* counts the integers '''k''' in the range '''1 ≤ k ≤ n''' for which the greatest common divisor '''gcd(n,k)''' is equal to '''1''' ::* counts numbers '''≤ n''' and prime to '''n'''

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

;Task: Create a '''totient''' function and: ::* Find and display (1 per line) for the 1st '''25''' integers: ::::* the integer (the index) ::::* the totient number for that integer ::::* indicate if that integer is prime ::* Find and display the ''count'' of the primes up to 100 ::* Find and display the ''count'' of the primes up to 1,000 ::* Find and display the ''count'' of the primes up to 10,000 ::* Find and display the ''count'' of the primes up to 100,000 (optional)

Show all output here.

;Related task: ::* [[Perfect totient numbers]]

;Also see: ::* the Wikipedia entry for [http://wikipedia.org/wiki/Euler's_totient_function Euler's totient function]. ::* the MathWorld entry for [http://mathworld.wolfram.com/TotientFunction.html totient function]. ::* the OEIS entry for [http://oeis.org/A000010 Euler totient function phi(n)].

## AWK

```
# syntax: GAWK -f TOTIENT_FUNCTION.AWK
BEGIN {
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)
}

```

{{out}}

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

}

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;
}
}
```

{{out}}

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

{{trans|Go}}

```dyalect
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
}
}

print("n\tphi\tprime")
var count = 0
for 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)")
}
}
```

{{out}}

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

```factor
USING: combinators formatting io kernel math math.primes.factors
math.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
```

{{out}}

```txt

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

{{trans|Pascal}}

```freebasic

#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 = result
End 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; cnt
End 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 idx
End Sub

Dim l As Integer
display(25)

Print Chr(10) & "   Limite  Son primos"
ContandoPrimos(25)
l = 100
Do
ContandoPrimos(l)
l = l*10
Loop Until l > 1000000
End

```

{{out}}

```txt

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.

```go
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++
}
}
}

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)
}
}
}
```

{{out}}

```txt

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:

```go
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
}
}

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.

{{trans|C}}

{-# LANGUAGE BangPatterns #-}

totient :: (Integral a) => a -> a
totient 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         = if m > 1 then tot - (tot `div` m) else tot
| m `mod` i == 0    = loop m' tot' i'
| otherwise         = loop m tot i'
where i'   = if i == 2 then 3 else (i + 2)
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'        = i + 1
tot       = totient i'
isPrime   = tot == i' - 1
count'    = if isPrime then count + 1 else count
when (i' <= 25) \$ do
putStrLn \$ (show i') ++ "\t" ++ (show tot) ++ "\t" ++ (show isPrime)
when (i' `elem` 25 : [ 10^k | k <- [2..6] ]) \$ do
putStrLn \$ "Number of primes up to " ++ (show i') ++ " = " ++ (show count')
loop (i + 1) count'
loop 0 0

```

{{out}}

```txt

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

```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. 25
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
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
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

NB. primes first exceeding the limits
[&.:(p:inv) 10 ^ 2 + i. 4
101 1009 10007 100003

p:inv 101 1009 10007 100003
25 168 1229 9592

NB. limit and prime count
(,. p:inv) 10 ^ 2 + i. 5
100    25
1000   168
10000  1229
100000  9592
1e6 78498

```

## Julia

{{trans|Python}}

```julia
φ(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
end
end

runphitests()

```
{{output}}
```txt

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

{{trans|Go}}

```scala
// 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
}

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}}

```txt

Same as Go example.

```

## Lua

Averages about 7 seconds under LuaJIT

```lua
-- Return the greatest common denominator of x and y
function gcd (x, y)
return y == 0 and math.abs(x) or gcd(y, x % y)
end

-- Return the totient number for n
function totient (n)
local count = 0
for k = 1, n do
if gcd(n, k) == 1 then count = count + 1 end
end
return count
end

-- Determine (inefficiently) whether p is prime
function isPrime (p)
end

-- Output totient and primality for the first 25 integers
print("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 10000
local pCount, i, limit = 0, 1
for 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
```

{{out}}

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

## Nim

```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 = 0
for 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}"
```

{{out}}

```txt

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

```pascal
{\$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);
end
end;
var
i : NativeUint;
Begin
display(25);

writeln('Limit  primecount');
i := 100;
repeat
OutCountPrimes(i);
i := i*10;
until i >100000;
end.
```

;Output:

```txt
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.

```pascal
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:

```txt

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 𝜑====
{{trans|Perl 6}}

```perl
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;
}

```

{{out}}

```txt
𝜑( 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.

```perl
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|2018.11}}
This is an ''incredibly'' inefficient way of finding prime numbers.

```perl6
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}
}
```

{{out}}

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

{{trans|Go}}

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

{{out}}

```txt

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

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

{{out}}

```txt

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

```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}")
```

{{out}}

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

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

{{out}}

```txt

φ(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
/*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*/
say
say right(primes, w)    ' primes detected for numbers up to and including '    N
exit                                             /*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 #
```

{{out|output|text=  when using the default input of:      25 }}

```txt

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

```

{{out|output|text=  when using the input of:      -100 }}

```txt

25  primes detected for numbers up to and including  100

```

{{out|output|text=  when using the input of:      -1000 }}

```txt

168  primes detected for numbers up to and including  1000

```

{{out|output|text=  when using the input of:      -10000 }}

```txt

1229  primes detected for numbers up to and including  10000

```

{{out|output|text=  when using the input of:      -1000000 }}

```txt

9592 primes detected for numbers up to and including  100000

```

## Ruby

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

```

{{out}}

```txt

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

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

```txt

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:

```scala
@tailrec
def 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:

```scala
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:

```scala
@tailrec
def scrub(f: Long, num: Long): Long = if(num%f == 0) scrub(f, num/f) else num
def 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.
{{out}}

```txt
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)'''.

```ruby
func 𝜑(n) {
n.factor_exp.prod {|p|
(p[0]-1) * p[0]**(p[1]-1)
}
}
```

```ruby
for n in (1..25) {
var totient = 𝜑(n)
printf("𝜑(%2s) = %3s%s\n", n, totient, totient==(n-1) ? ' - prime' : '')
}
```

{{out}}
𝜑( 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

```

```ruby
[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}"
}
```

{{out}}

```txt

Number of primes <= 100: 25
Number of primes <= 1000: 168
Number of primes <= 10000: 1229
Number of primes <= 100000: 9592

```

## VBA

{{trans|Phix}}
```vb
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 = tot
End 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 n
End Sub
```
{{out}}

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

```zkl
fcn totient(n){ [1..n].reduce('wrap(p,k){ p + (n.gcd(k)==1) }) }
fcn isPrime(n){ totient(n)==(n - 1) }
```

```zkl
foreach n in ([1..25]){
println("\u03c6(%2d) ==%3d %s"
.fmt(n,totient(n),isPrime(n) and "is prime" or ""));
}
```

{{out}}
φ( 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

```

```zkl
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));
}
```

{{out}}

```txt

Primes <=    100 :    25
Primes <=  1,000 :   168
Primes <= 10,000 : 1,229

```

```