include "cowgol.coh";

sub totient(n: uint32): (tot: uint32) is
    tot := n;

    var i: uint32 := 2;
    while i*i <= n loop
        if n%i == 0 then
            while n%i == 0 loop
                n := n/i;
            end loop;
            tot := tot - tot/i;
        end if;
        if i == 2 then
            i := 1;
        end if;
        i := i + 2;
    end loop;

    if n > 1 then
        tot := tot - tot/n;
    end if;
end sub;

var count: uint16 := 0;

print("N\tTotient\tPrime\n");
var n: uint32 := 1;
while n <= 25 loop
    var tot := totient(n);
    print_i32(n);
    print_char('\t');
    print_i32(tot);
    print_char('\t');
    if n-1 == tot then
        count := count + 1;
        print("Yes\n");
    else
        print("No\n");
    end if;
    n := n + 1;
end loop;

print("Number of primes up to 25:\t");
print_i16(count);
print_nl();

while n <= 100000 loop
    tot := totient(n);
    if n-1 == tot then
        count := count + 1;
    end if;
    if n == 100 or n == 1000 or n % 10000 == 0 then
        print("Number of primes up to ");
        print_i32(n);
        print(":\t");
        print_i16(count);
        print_nl();
    end if;
    n := n + 1;
end loop;