Rosetta Code

Category talk:Wren-math: Difference between revisions

Category Discussion

Category talk:Wren-math (view source)

Revision as of 14:42, 17 October 2022

1,062 bytes removed ,  1 year ago
→‎Source code: Replaced Int.primeCount method with a non-memoized version.
(→‎Source code: Added a second 'divisors' method which is quicker for large numbers with a small number of prime factors.)
(→‎Source code: Replaced Int.primeCount method with a non-memoized version.)
Line 311:
 
// Private helper method which counts and returns how many primes there are
// up to and including 'n' using the Legendre method.
static legendre_(n, primesa, memoPhiprimes) {
if (na <= 21) return 0(a < 1) ? n : n - (n >> 1)
var phipa = primes[a-1]
phiif =(n Fn.new<= {pa) |x,return a|1
return legendre_(n, a-1, primes) if- legendre_(a == 0(n/pa).floor, returna-1, xprimes)
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
}
 
// Computes, using ana appropriatesuitable method, and returns how many primes there are ▼
// 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
var k = ((n-3)/2).floor + 1
var marked = List.filled(k, true)
var limit = ((n.sqrt.floor - 3)/2).floor + 1
limit = limit.max(0)
for (i in 0...limit) {
if (marked[i]) {
var p = 2*i + 3
var s = ((p*p - 3)/2).floor
var j = s
while (j < k) {
marked[j] = false
j = j + p
}
}
}
for (i in 0...k) {
if (marked[i]) count = count + 1
}
return count
}
 
▲ // Computes, using an appropriate method, and returns how many primes there are
// up to and including 'n'.
static primeCount(n) {
if (n < 1e43) return primeCountSmall_(n < 2) ? 0 : 1
var limit = n.sqrt.floor
var primes = primeSieve(limit)
var memoPhia = {}primes.count
return legendre_(n, primesa, memoPhiprimes) + a - 1
}
 
PureFox
9,482

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/332266"