Category talk:Wren-math: Difference between revisions
Content added Content deleted
m (→Source code: Removed some trailing whitespace introduced by last edit.) |
(→Source code: Replaced Int.primeCount with a much quicker version.) |
||
Line 329: | Line 329: | ||
} |
} |
||
// Computes |
// Computes and returns how many primes there are up to and including 'n'. |
||
// See https://rosettacode.org/wiki/Legendre_prime_counting_function for details. |
|||
// up to and including 'n'. Can optionally use memoization to improve performance. |
|||
static primeCount(n |
static primeCount(n) { |
||
if (n < 3) return (n < 2) ? 0 : 1 |
if (n < 3) return (n < 2) ? 0 : 1 |
||
if (n < 9) return ((n + 1)/2).floor |
|||
var |
var masks = [1, 2, 4, 8, 16, 32, 64, 128] |
||
var |
var half = Fn.new { |n| (n - 1) >> 1 } |
||
var rtlmt = n.sqrt.floor |
|||
return (memoize ? phi_(n, a, primes, {}) : phi_(n, a, primes)) + a - 1 |
|||
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 |
|||
} |
} |
||
// Convenience version of primeCount which always uses memoization. |
|||
static primeCount(n) { primeCount(n, true) } |
|||
// Returns the prime factors of 'n' in order using a wheel with basis [2, 3, 5]. |
// Returns the prime factors of 'n' in order using a wheel with basis [2, 3, 5]. |