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


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