37 lines
938 B
Plaintext
37 lines
938 B
Plaintext
program totient;
|
|
loop for n in [1..1000000] do
|
|
tot := totient(n);
|
|
if tot = n-1 then prime +:= 1; end if;
|
|
|
|
if n <= 25 then
|
|
print(lpad(str n, 2), " ",
|
|
lpad(str tot, 2), " ",
|
|
if tot = n-1 then "prime" else "" end if);
|
|
end if;
|
|
|
|
if n in [1000,10000,100000,1000000] then
|
|
print(lpad(str prime,8), "primes up to" + lpad(str n,8));
|
|
end if;
|
|
end loop;
|
|
|
|
proc totient(n);
|
|
tot := n;
|
|
i := 2;
|
|
loop while i*i <= n do
|
|
if n mod i = 0 then
|
|
loop while n mod i = 0 do
|
|
n div:= i;
|
|
end loop;
|
|
tot -:= tot div i;
|
|
end if;
|
|
if i=2 then i:=3;
|
|
else i+:=2;
|
|
end if;
|
|
end loop;
|
|
if n>1 then
|
|
tot -:= tot div n;
|
|
end if;
|
|
return tot;
|
|
end proc;
|
|
end program;
|