Category talk:Wren-math: Difference between revisions
Content deleted Content added
→Source code: primeSieve and primeCount should be static methods. |
→Source code: primeCount method now uses Legendre algorithm for large numbers of primes. |
||
Line 190:
// Convenience version of above method which uses true for the primesOnly parameter.
static primeSieve(
//
// up to and including 'n' using the Legendre method.
static primeCount(n) {▼
static legendre_(n, primes, memoPhi) {
if (n < 2) return 0
var phi
phi = Fn.new { |x, a|
if (a == 0) return x
var key = cantorPair(x, a)
if (memoPhi.containsKey(key)) return memoPhi[key]
var pa = primes[a-1]
return memoPhi[key] = phi.call(x, a-1) - phi.call((x/pa).floor, a-1)
}
var a = legendre_(n.sqrt.floor, primes, memoPhi)
return phi.call(n, a) + a - 1
}
// Private helper method which sieves for primes up to and including 'n'
// and returns how many there are. Faster than Legendre method for small n.
static primeCountSmall_(n) {
if (n < 2) return 0
var count = 1
Line 215 ⟶ 232:
}
return count
}
// Computes, using an appropriate method, and returns how many primes there are
// up to and including 'n'.
▲ static primeCount(n) {
if (n < 1e4) return primeCountSmall_(n)
var limit = n.sqrt.floor
var primes = primeSieve(limit)
var memoPhi = {}
return legendre_(n, primes, memoPhi)
}
| |||