scope # Totient function

    # returns the number of integers k where 1 <= k <= n that are mutually prime to n
    local procedure totient( n :: number ) :: number
        if   n < 3 then result := 1
        elif n = 3 then result := 2
        else
            result := n;
            local v, i := n, 2;
            while i * i <= v do
                if v mod i = 0 then
                    while v mod i = 0 do v \:= i od;
                    result -:= result \ i
                fi;
                if i = 2 then
                    i := 1
                fi;
                i +:= 2
            od;
            if v > 1 then result -:= result \ v fi;
        fi;
        return result
    end;

    # show the totient function values for the first 25 integers
    io.write( " n  phi(n) remarks\n" );
    for n to 25 do
        local constant tn := totient( n );
        printf( "%2d: %5d%s\n", n, tn, if tn = n - 1 and tn <> 0 then "  n is prime" else "" fi )
    od;

    # use the totient function to count primes
    local n100, n1_000, n10_000, n100_000 := 0, 0, 0, 0;
    for n to 100_000 do
        if totient( n ) = n - 1 then
            if n <=    100 then     n100 +:= 1 fi;
            if n <=   1000 then   n1_000 +:= 1 fi;
            if n <=  10000 then  n10_000 +:= 1 fi;
            if n <= 100000 then n100_000 +:= 1 fi
        fi
    od;
    printf( "There are %6d primes below      100\n",     n100 );
    printf( "There are %6d primes below    1 000\n",   n1_000 );
    printf( "There are %6d primes below   10 000\n",  n10_000 );
    printf( "There are %6d primes below  100 000\n", n100_000 )
end