Category talk:Wren-math: Difference between revisions
→Source code: Int.primeCount now optionally allows for memoization.
(→Source code: Replaced Int.primeCount method with a non-memoized version.) |
(→Source code: Int.primeCount now optionally allows for memoization.) |
||
Line 312:
// Private helper method which counts and returns how many primes there are
// up to and including 'n' using the Legendre method.
static
if (a <= 1) return (a < 1) ? n : n - (n >> 1)
var pa = primes[a-1]
if (n <= pa) return 1
return
}
// As above method but uses memoization.
static phi_(n, a, primes, cache) {
if (a <= 1) return (a < 1) ? n : n - (n >> 1)
var pa = primes[a-1]
if (n <= pa) return 1
var key = Int.cantorPair(n, a)
if (cache.containsKey(key)) return cache[key]
return cache[key] = phi_(n, a-1, primes, cache) - phi_((n/pa).floor, a-1, primes, cache)
}
// Computes, using a suitable method, and returns how many primes there are
// up to and including 'n'. Can optionally use memoization to improve performance.
static primeCount(n, memoize) {
if (n < 3) return (n < 2) ? 0 : 1
var limit = n.sqrt.floor
var primes = primeSieve(limit)
var a = primes.count
return
}
// 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].
| |||