47 lines
1.4 KiB
Text
47 lines
1.4 KiB
Text
with javascript_semantics
|
|
--
|
|
-- While a phix dictionary can handle keys of {x,a}, for this
|
|
-- task performance was dreadful (7,612,479 entries, >3mins),
|
|
-- so instead memophix maps known x to an index to memophia
|
|
-- which holds the full [1..a] for each x, dropping to a much
|
|
-- more respectable (albeit not super-fast) 9.5s
|
|
--
|
|
constant memophix = new_dict()
|
|
sequence memophia = {} -- 1..a (max 3401) for each x
|
|
|
|
function phi(integer x, a)
|
|
if a=0 then return x end if
|
|
integer adx = getd(x,memophix), res
|
|
if adx=NULL then
|
|
memophia = append(memophia,repeat(-1,a))
|
|
adx = length(memophia)
|
|
setd(x,adx,memophix)
|
|
else
|
|
object ma = memophia[adx]
|
|
integer l = length(ma)
|
|
if a>l then
|
|
memophia[adx] = 0 -- kill refcount
|
|
memophia[adx] = ma & repeat(-1,a-l)
|
|
else
|
|
res = ma[a]
|
|
if res>=0 then return res end if
|
|
end if
|
|
ma = 0 -- kill refcount
|
|
end if
|
|
res = phi(x, a-1) - phi(floor(x/get_prime(a)), a-1)
|
|
memophia[adx][a] = res
|
|
return res
|
|
end function
|
|
|
|
function pi(integer n)
|
|
if n<2 then return 0 end if
|
|
integer a = pi(floor(sqrt(n)))
|
|
return phi(n, a) + a - 1
|
|
end function
|
|
|
|
atom t0 = time()
|
|
for i=0 to iff(platform()=JS?8:9) do
|
|
printf(1,"10^%d %d\n",{i,pi(power(10,i))})
|
|
-- printf(1,"10^%d %d\n",{i,length(get_primes_le(power(10,i)))})
|
|
end for
|
|
?elapsed(time()-t0)
|