Category talk:Wren-long: Difference between revisions

Content added Content deleted

Inline

@@ Line 1,015: / Line 1,015: @@
     // As 'divisors' method but uses a different algorithm.
-    // Better for large numbers with a small number of prime factors.
+    // Better for larger numbers.
     static divisors2(n) {
-        if (n == ULong.zero) return []
+        if (n is Num) n = ULong.new(n)
-        var factors = ULong.primeFactors(n)
+        var pf = ULong.primeFactors(n)
-        var divs = [ULong.one]
+        if (pf.count == 0) return (n == 1) ? [one] : pf
-        for (p in factors) {
+        var arr = []
-            for (i in 0...divs.count) divs.add(divs[i]*p)
+        if (pf.count == 1) {
+            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])
         }
-        divs.sort()
+        var divisors = []
-        var c = divs.count
+        var generateDivs
-        if (c > 1) {
+        generateDivs = Fn.new { |currIndex, currDivisor|
-            for (i in c-1..1) {
+            if (currIndex == arr.count) {
-                if (divs[i-1] == divs[i]) divs.removeAt(i)
+                divisors.add(currDivisor.copy())
+                return
+            }
+            for (i in 0..arr[currIndex][1]) {
+                generateDivs.call(currIndex+1, currDivisor)
+                currDivisor = currDivisor * arr[currIndex][0]
             }
         }
-        return divs
+        generateDivs.call(0, one)
+        return divisors.sort()
     }
@@ Line 1,038: / Line 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
     }
 }