local function totient(n)
    local tot = n
    local i = 2
    while i * i <= n do
        if n % i == 0 then
            while n % i == 0 do n //= i end
            tot -=  tot // i
        end
        if i == 2 then i = 1 end
        i += 2
    end
    if n > 1 do tot -= tot // n end
    return tot
end

print(" n  phi   prime")
print("---------------")
local count = 0
for n = 1, 25 do
    local tot = totient(n)
    local isPrime = (n - 1) == tot
    if isPrime then ++count end
    print(string.format("%2d   %2d   %s", n, tot, isPrime))
end
print("\nNumber of primes up to 25     = " .. count)
for n = 26, 100_000 do
    local tot = totient(n)
    if tot == n - 1 then ++count end
    if n == 100 or n == 1_000 or n % 10_000 == 0 then
        local ns = string.format("%-6d", n)
        print($"\nNumber of primes up to {ns} = {count}")
    end
end