The   totient   function is also known as:

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


Definitions   (as per number theory)

The totient function:

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


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



Task

Create a   totient   function and:

   Find and display   (1 per line)   for the 1st   25   integers:
   the integer   (the index)
   the totient number for that integer
   indicate if that integer is prime
   Find and display the   count   of the primes up to          100
   Find and display the   count   of the primes up to       1,000
   Find and display the   count   of the primes up to     10,000
   Find and display the   count   of the primes up to   100,000     (optional)
Show all output here.



Related task

   Perfect totient numbers


Also see

   Wikipedia: Euler's totient function.
   MathWorld: totient function.
   OEIS: Euler totient function phi(n).


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