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


 
#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
