38 lines
867 B
Plaintext
38 lines
867 B
Plaintext
with javascript_semantics
|
|
atom t0 = time()
|
|
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")
|
|
for n=1 to 25 do
|
|
integer tot = totient(n)
|
|
bool prime = (n-1=tot)
|
|
printf(1,"%2d %2d %t\n",{n,tot,prime})
|
|
end for
|
|
printf(1,"\n")
|
|
integer count = 0
|
|
for n=1 to 1e6 do
|
|
-- count += (totient(n)=n-1)
|
|
count += (phi(n)=n-1)
|
|
if find(n,{25,1e2,1e3,1e4,1e5,1e6,1e7}) then
|
|
printf(1,"Number of primes up to %d = %d\n",{n,count})
|
|
end if
|
|
end for
|
|
?elapsed(time()-t0)
|