Category talk:Wren-math: Difference between revisions
→Source code: Replaced Int.primeCount with a much quicker version.
m (→Source code: Removed some trailing whitespace introduced by last edit.) |
(→Source code: Replaced Int.primeCount with a much quicker version.) |
||
Line 329:
}
// Computes
// See https://rosettacode.org/wiki/Legendre_prime_counting_function for details.
static primeCount(n
if (n < 3) return (n < 2) ? 0 : 1
var
var
var rtlmt = n.sqrt.floor
var mxndx = Int.quo(rtlmt - 1, 2)
var arrlen = (mxndx + 1).min(2)
var smalls = List.filled(arrlen, 0)
var roughs = List.filled(arrlen, 0)
var larges = List.filled(arrlen, 0)
for (i in 0...arrlen) {
smalls[i] = i
roughs[i] = i + i + 1
larges[i] = Int.quo(Int.quo(n, i + i + 1) - 1 , 2)
}
var cullbuflen = Int.quo(mxndx + 8, 8)
var cullbuf = List.filled(cullbuflen, 0)
var nbps = 0
var rilmt = arrlen
var i = 1
while (true) {
var sqri = (i + i) * (i + 1)
if (sqri > mxndx) break
if ((cullbuf[i >> 3] & masks[i & 7]) != 0) {
i = i + 1
continue
}
cullbuf[i >> 3] = cullbuf[i >> 3] | masks[i & 7]
var bp = i + i + 1
var c = sqri
while (c < arrlen) {
cullbuf[c >> 3] = cullbuf[c >> 3] | masks[c & 7]
c = c + bp
}
var nri = 0
for (ori in 0...rilmt) {
var r = roughs[ori]
var rci = r >> 1
if ((cullbuf[rci >> 3] & masks[rci & 7]) != 0) continue
var d = r * bp
var t = (d <= rtlmt) ? larges[smalls[d >> 1] - nbps] :
smalls[half.call(Int.quo(n, d))]
larges[nri] = larges[ori] - t + nbps
roughs[nri] = r
nri = nri + 1
}
var si = mxndx
var pm = ((rtlmt/bp).floor - 1) | 1
while (pm >= bp) {
var c = smalls[pm >> 1]
var e = (pm * bp) >> 1
while (si >= e) {
smalls[si] = smalls[si] - c + nbps
si = si - 1
}
pm = pm - 2
}
rilmt = nri
nbps = nbps + 1
i = i + 1
}
var ans = larges[0] + ((rilmt + 2 * (nbps - 1)) * (rilmt - 1) / 2).floor
for (ri in 1...rilmt) ans = ans - larges[ri]
var ri = 1
while (true) {
var p = roughs[ri]
var m = Int.quo(n, p)
var ei = smalls[half.call(Int.quo(m, p))] - nbps
if (ei <= ri) break
ans = ans - (ei - ri) * (nbps + ri - 1)
for (sri in (ri + 1..ei)) {
ans = ans + smalls[half.call(Int.quo(m, roughs[sri]))]
}
ri = ri + 1
}
return ans + 1
}
// Returns the prime factors of 'n' in order using a wheel with basis [2, 3, 5].
| |||