39 lines
865 B
Plaintext
39 lines
865 B
Plaintext
with javascript_semantics
|
|
atom t0 = time()
|
|
constant maxphi = 1e7
|
|
sequence s_phi
|
|
procedure computePhi()
|
|
s_phi = tagset(maxphi)
|
|
for i=2 to maxphi do
|
|
if s_phi[i]=i then
|
|
for j=i to maxphi by i do
|
|
s_phi[j] -= s_phi[j] / i;
|
|
end for
|
|
end if
|
|
end for
|
|
end procedure
|
|
|
|
function countPrimes(int lo, hi)
|
|
int count = 0;
|
|
for i=lo to hi do
|
|
if s_phi[i] == i-1 then
|
|
count += 1
|
|
end if
|
|
end for
|
|
return count;
|
|
end function
|
|
|
|
computePhi()
|
|
printf(1," n phi prime\n")
|
|
printf(1," --------------\n")
|
|
for n=1 to 25 do
|
|
integer tot = s_phi[n]
|
|
bool prime = (n-1=tot)
|
|
printf(1,"%2d %2d %t\n",{n,tot,prime})
|
|
end for
|
|
printf(1,"\n")
|
|
for n in {25,1e2,1e3,1e4,1e5,1e6,1e7} do
|
|
printf(1,"Number of primes up to %d = %d\n",{n,countPrimes(1,n)})
|
|
end for
|
|
?elapsed(time()-t0)
|