Legendre prime counting function: Difference between revisions

Content added Content deleted
m (→‎{{header|Julia}}: add trans from nim)
m (use the precalculated values from Nim example)
Line 2,060: Line 2,060:
{{trans|Nim}}
{{trans|Nim}}
<syntaxhighlight lang="julia">
<syntaxhighlight lang="julia">
const masks = [1, 2, 4, 8, 16, 32, 64, 128]
⚫
function countprimes(n::Integer)

⚫
n < 3 && return typeof(n)(n > 1)
⚫
function countprimes(n)
@inline half(i::Integer) = (i - 1) >> 1
⚫
n < 3 && return n > 1
rtlmt = isqrt(n)
rtlmt = isqrt(n)
mxndx = (rtlmt - 1) ÷ 2
mxndx = (rtlmt - 1) ÷ 2
smalls = [i for i in 0:mxndx+1]
rilmt = mxndx + 1
roughs = [i + i + 1 for i in 0:mxndx+1]
smalls = [i for i in 0:rilmt]
larges = [(n ÷ (i + i + 1) - 1) ÷ 2 for i in 0:mxndx+1]
roughs = [i + i + 1 for i in 0:rilmt]
cmpsts = falses(mxndx + 1)
larges = [(n ÷ (i + i + 1) - 1) ÷ 2 for i in 0:rilmt]
bp, npc, mxri = 3, 0, mxndx
cullbuf = zeros(Int, (mxndx + 8) ÷ 8)
while true
nbps = 0
i = bp >> 1
for i in 1:typemax(UInt32)
sqri = (i + i) * (i + 1)
sqri = (i + i) * (i + 1)
sqri > mxndx && break
sqri > mxndx && break
if !cmpsts[i + 1]
cullbuf[i >> 3 + 1] & masks[i & 7 + 1] != 0 && continue
cmpsts[i + 1] = true
cullbuf[i >> 3 + 1] |= masks[i & 7 + 1]
for c in sqri:bp:mxndx
bp = i + i + 1
cmpsts[c + 1] = true
for c in sqri:bp:arrlen-1
⚫
cullbuf[c >> 3 + 1] |= masks[c & 7 + 1]
⚫
end
⚫
nri = 0
⚫
for ori in 0:rilmt-1
⚫
r = roughs[ori + 1]
⚫
rci = r >> 1
cullbuf[rci >> 3 + 1] & masks[rci & 7 + 1] != 0 && continue
⚫
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
ri = 0
larges[nri + 1] = larges[ori + 1] - t + nbps
for k in 0:mxri
roughs[nri + 1] = r
q = roughs[k + 1]
nri += 1
qi = q >> 1
end
cmpsts[qi + 1] && continue
si = mxndx
d = bp * q
for pm in (rtlmt ÷ bp - 1) | 1 : -2 : bp
larges[ri + 1] = larges[k + 1] + npc -
c = smalls[pm>>1 + 1]
(d <= rtlmt ? larges[smalls[d >> 1 + 1] - npc + 1] : smalls[half(n ÷ d) + 1])
e = (pm * bp) >> 1
roughs[ri + 1] = q
while si >= e
ri += 1
smalls[si + 1] -= (c - nbps)
⚫
si -= 1
end
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
end
bp += 2
rilmt = nri
⚫
nbps += 1
end
end
ans = larges[1] + ((rilmt + 2*(nbps-1)) * (rilmt - 1) ÷ 2)

result = larges[1]
for ri in 1:rilmt-1
for i in 2:mxri+1
ans -= larges[ri + 1]
⚫
result -= larges[i]
end
end
for ri in 1:typemax(UInt32)
result += (mxri + 1 + 2 * (npc - 1)) * mxri ÷ 2
p = roughs[ri + 1]

⚫
for j in 1:mxri
⚫
p = roughs[j + 1]
m = n ÷ p
m = n ÷ p
ee = smalls[half(m ÷ p) + 1] - npc
ei = smalls[((m ÷ p) - 1) >> 1 + 1] - nbps
ee <= j && break
ei <= ri && break
for k in j+1:ee
ans -= (ei - ri) * (nbps + ri - 1)
for sri in ri+1:ei
result += smalls[half(m ÷ roughs[k + 1]) + 1]
ans += smalls[(m ÷ (roughs[sri + 1]) - 1) >> 1 + 1]
end
end
⚫
result -= (ee - j) * (npc + j - 1)
end
end
return result + 1
return ans + 1
end
end


Retrieved from "https://rosettacode.org/wiki/Legendre_prime_counting_function"