(phixonline)-->
function totient(integer n)
integer tot = n, i = 2
while i*i<=n do
if mod(n,i)=0 then
while true do
n /= i
if mod(n,i)!=0 then exit end if
end while
tot -= tot/i
end if
i += iff(i=2?1:2)
end while
if n>1 then
tot -= tot/n
end if
return tot
end function
printf(1," n phi prime\n")
printf(1," --------------\n")
integer count = 0
for n=1 to 25 do
integer tot = totient(n),
prime = (n-1=tot)
count += prime
string isp = iff(prime?"true":"false")
printf(1,"%2d %2d %s\n",{n,tot,isp})
end for
printf(1,"\nNumber of primes up to 25 = %d\n",count)
for n=26 to 100000 do
count += (totient(n)=n-1)
if find(n,{100,1000,10000,100000}) then
printf(1,"Number of primes up to %-6d = %d\n",{n,count})
end if
end for