Proper divisors: Difference between revisions

Content added Content deleted

Inline

@@ Line 3,762: / Line 3,762: @@
 ===Proper divisors for big (long) numbers===
-<lang Scala>import annotation.tailrec
+<lang Scala>import scala.annotation.tailrec
-import collection.parallel.mutable.ParSeq
-def factorize(n: Long): List[Long] = {
+def factorize(x: BigInt): List[BigInt] = {
-    @tailrec
+  @tailrec
-    def factors(tuple: (Long, Long, List[Long], Int)): List[Long] = {
+  def foo(x: BigInt, a: BigInt = 2, list: List[BigInt] = Nil): List[BigInt] = a * a > x match {
+    case false if x % a == 0 => foo(x / a, a, a :: list)
-        tuple match {
+    case false => foo(x, a + 1, list)
-            case (1, _, acc, _)                 => acc
+    case true => x :: list
-            case (n, k, acc, _) if (n % k == 0) => factors((n / k, k, acc ++ ParSeq(k), Math.sqrt(n / k).toInt))
+  }
-            case (n, k, acc, sqr) if (k < sqr)  => factors(n, k + 1, acc, sqr)
-            case (n, k, acc, sqr) if (k >= sqr) => factors((1, k, acc ++ ParSeq(n), 0))
-        }
+  foo(x)
-    }
-    factors((n, 2, List[Long](), Math.sqrt(n).toInt))
 }
-def properDivisors(n: Long) = {
+def properDivisors(n: BigInt): List[BigInt] = {
-    val factors = factorize(n)
+  val factors = factorize(n)
-    val products = (1 until factors.length).map(i =>
-        factors.combinations(i).map(_.product).toList).flatten
+  val products = (1 until factors.length).flatMap(i => factors.combinations(i).map(_.product).toList).toList
-    (1L +: products).filter(_ < n)
+  (BigInt(1) :: products).filter(_ < n)
 }</lang>