Legendre prime counting function: Difference between revisions
Content added Content deleted
(→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: | Line 2,056: | ||
10^9 50847534 |
10^9 50847534 |
||
0.003234 seconds (421 allocations: 14.547 KiB) |
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> |
</pre> |
||