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


     REM PRINT THE DATA FOR N=1 TO 25
     LET N = 0
  10 LET N = N + 1
     IF N = 26 THEN GOTO 100
     GOSUB 1000
     IF T = N - 1 THEN LET P = 1
     IF T <> N - 1 THEN LET P = 0
     PRINT N," ", T," ",P
     GOTO 10
 100 REM COUNT PRIMES BELOW 10000
     LET C = 0
     LET N = 2
 110 GOSUB 1000
     IF T = N - 1 THEN LET C = C + 1
     IF N = 100 THEN PRINT "There are ", C, " primes below 100."
     IF N = 1000 THEN PRINT "There are ", C, " primes below 1000."
     IF N = 10000 THEN PRINT "There are ", C, " primes below 10000."
     LET N = N + 1
     IF N < 10001 THEN GOTO 110
     END
1000 REM TOTIENT FUNCTION OF INTEGER N
     LET M = 1
     LET T = 0
1010 IF M > N THEN RETURN
     LET A = N
     LET B = M    REM NEED TO RENAME THESE SO THEY ARE PRESERVED
     GOSUB 2000
     IF G = 1 THEN LET T = T + 1
     LET M = M + 1
     GOTO 1010
2000 REM GCD OF INTEGERS A, B
2010 IF A>B THEN GOTO 2020
     LET B = B - A
     IF A=0 THEN LET G = B
     IF A=0 THEN RETURN
2020 LET S = A
     LET A = B
     LET B = S
     GOTO 2010