Legendre prime counting function: Difference between revisions
m
→{{header|Julia}}: add trans from nim
(→Iterative, partial sieving: Changed 2 variable names to align with V of which it is a translation.) |
m (→{{header|Julia}}: add trans from nim) |
||
Line 2,056:
10^9 50847534
0.003234 seconds (421 allocations: 14.547 KiB)
</pre>
=== nonrecursive method ===
{{trans|Nim}}
<syntaxhighlight lang="julia">
function countprimes(n::Integer)
n < 3 && return typeof(n)(n > 1)
@inline half(i::Integer) = (i - 1) >> 1
rtlmt = isqrt(n)
mxndx = (rtlmt - 1) ÷ 2
smalls = [i for i in 0:mxndx+1]
roughs = [i + i + 1 for i in 0:mxndx+1]
larges = [(n ÷ (i + i + 1) - 1) ÷ 2 for i in 0:mxndx+1]
cmpsts = falses(mxndx + 1)
bp, npc, mxri = 3, 0, mxndx
while true
i = bp >> 1
sqri = (i + i) * (i + 1)
sqri > mxndx && break
if !cmpsts[i + 1]
cmpsts[i + 1] = true
for c in sqri:bp:mxndx
cmpsts[c + 1] = true
end
ri = 0
for k in 0:mxri
q = roughs[k + 1]
qi = q >> 1
cmpsts[qi + 1] && continue
d = bp * q
larges[ri + 1] = larges[k + 1] + npc -
(d <= rtlmt ? larges[smalls[d >> 1 + 1] - npc + 1] : smalls[half(n ÷ d) + 1])
roughs[ri + 1] = q
ri += 1
end
m = mxndx
for k in (rtlmt ÷ bp - 1) | 1 : -2 : bp
c = smalls[k >> 1 + 1] - npc
ee = (k * bp) >> 1
while m >= ee
smalls[m + 1] -= c
m -= 1
end
end
mxri = ri - 1
npc += 1
end
bp += 2
end
result = larges[1]
for i in 2:mxri+1
result -= larges[i]
end
result += (mxri + 1 + 2 * (npc - 1)) * mxri ÷ 2
for j in 1:mxri
p = roughs[j + 1]
m = n ÷ p
ee = smalls[half(m ÷ p) + 1] - npc
ee <= j && break
for k in j+1:ee
result += smalls[half(m ÷ roughs[k + 1]) + 1]
end
result -= (ee - j) * (npc + j - 1)
end
return result + 1
end
for i in 0:14
println("π(10^$i) = ", countprimes(10^i))
end
</syntaxhighlight>{{out}}
<pre>
π(10^0) = 0
π(10^1) = 4
π(10^2) = 25
π(10^3) = 168
π(10^4) = 1229
π(10^5) = 9592
π(10^6) = 78498
π(10^7) = 664579
π(10^8) = 5761455
π(10^9) = 50847534
π(10^10) = 455052511
π(10^11) = 4118054813
π(10^12) = 37607912018
π(10^13) = 346065536839
π(10^14) = 3204941750802
</pre>
| |||