Legendre prime counting function: Difference between revisions
m
→nonrecursive method
m (use the precalculated values from Nim example) |
|||
Line 2,063:
function countprimes(n)
n < 3 && return typeof(n)(n > 1)
rtlmt = isqrt(n)
mxndx = (rtlmt - 1) ÷ 2
smalls::Array{UInt32} = [i for i in 0:mxndx+1]
sqri = (i + i) * (i + 1)
sqri > mxndx && break
cullbuf[c >> 3 + 1] |= masks[c & 7 + 1]▼
end▼
nri = 0▼
for ori in 0:rilmt-1▼
r = roughs[ori + 1]▼
rci = r >> 1▼
d = r * bp▼
t = 0▼
if d <= rtlmt▼
t = larges[smalls[d>>1 + 1] - nbps + 1]▼
else▼
t = smalls[(n ÷ d - 1) >> 1 + 1]▼
end
end
for k in (rtlmt ÷ bp - 1) | 1 : -2 : bp
▲ end
end
nbps += 1▼
end
for i in
end
result += (mxri + 1 + 2 * (npc - 1)) * mxri ÷ 2
m = n ÷ p
▲ ans += smalls[(m ÷ (roughs[sri + 1]) - 1) >> 1 + 1]
end
result -= (ee - j) * (npc + j - 1)
end
return
end
Line 2,129:
println("π(10^$i) = ", countprimes(10^i))
end
@time countprimes(10^14)
</syntaxhighlight>{{out}}
<pre>
Line 2,146 ⟶ 2,149:
π(10^13) = 346065536839
π(10^14) = 3204941750802
4.744442 seconds (13 allocations: 153.185 MiB, 0.16% gc time)
</pre>
| |||