Category talk:Wren-math: Difference between revisions

Content added Content deleted

Inline

@@ Line 632: / Line 632: @@
     // 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 <= 0) return []
+        var pf = Int.primeFactors(n)
-        var factors = Int.primeFactors(n)
+        if (pf.count == 0) return (n == 1) ? [1] : pf
-        var divs = [1]
+        var arr = []
-        for (p in factors) {
+        if (pf.count == 1) {
-            for (i in 0...divs.count) divs.add(divs[i]*p)
+            arr.add([pf[0], 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, count])
+                    prevPrime = pf[i]
+                    count = 1
+                }
+            }
+            arr.add([prevPrime, 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)
+                return
+            }
+            for (i in 0..arr[currIndex][1]) {
+                generateDivs.call(currIndex+1, currDivisor)
+                currDivisor = currDivisor * arr[currIndex][0]
             }
         }
-        return divs
+        generateDivs.call(0, 1)
+        return divisors.sort()
     }