62 lines
1.2 KiB
Plaintext
62 lines
1.2 KiB
Plaintext
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;
|