Category talk:Wren-long: Difference between revisions
→Source code: Improved algorithm for ULong.divisors2 and added divisorSum and divisorCount methods.
(→Source code: Added modInv, improved isPrime.) |
(→Source code: Improved algorithm for ULong.divisors2 and added divisorSum and divisorCount methods.) |
||
Line 1,015:
// As 'divisors' method but uses a different algorithm.
// Better for
static divisors2(n) {
if (n
var
arr.add([pf[0].copy(), 1])
} else {
var prevPrime = pf[0]
var count = 1
for (i in 1...pf.count) {
if (pf[i] == prevPrime) {
count = count + 1
} else {
arr.add([prevPrime.copy(), count])
prevPrime = pf[i]
count = 1
}
}
arr.add([prevPrime.copy(), count])
}
var
return
}
for (i in 0..arr[currIndex][1]) {
generateDivs.call(currIndex+1, currDivisor)
currDivisor = currDivisor * arr[currIndex][0]
}
}
return divisors.sort()
}
Line 1,038 ⟶ 1,058:
var c = d.count
return (c <= 1) ? [] : d[0..-2]
}
// Returns the sum of all the divisors of 'n' including 1 and 'n' itself.
static divisorSum(n) {
if (n < 1) return 0
if (n is Num) n = ULong.new(n)
var total = one
var power = two
while (n % 2 == 0) {
total = total + power
power = power * 2
n = n / 2
}
var i = three
while (i * i <= n) {
var sum = one
power = i
while (n % i == 0) {
sum = sum + power
power = power * i
n = n / i
}
total = total * sum
i = i + 2
}
if (n > 1) total = total * (n + 1)
return total
}
// Returns the number of divisors of 'n' including 1 and 'n' itself.
static divisorCount(n) {
if (n < 1) return 0
if (n is Num) n = ULong.new(n)
var count = 0
var prod = 1
while (n % 2 == 0) {
count = count + 1
n = n / 2
}
prod = prod * (1 + count)
var i = three
while (i * i <= n) {
count = 0
while (n % i == 0) {
count = count + 1
n = n / i
}
prod = prod * (1 + count)
i = i + 2
}
if (n > 2) prod = prod * 2
return prod
}
}
| |||