Count divisors algorithm in immutable/pure functional Scala by William Narmontas (Scala Algorithm #3)

Problem

\(1\) has only 1 factor - \(1\), \(6\) has 4 - \(1, 2, 3, 6\), \(36\) has 9 - \(1, 2, 3, 4, 6, 9, 12, 18, 36\). It's similar to problems on:

Solution

View on Scastie (online Scala code playground, in a new window) if you would like to play around with this code, run it, add new test cases, all from your web browser without installing Scala.

def countDivisorsFor(n: Int): Int = {
  def nIsSquareOf(i: Int) = i * i == n
  def nHasFactor(i: Int) = n % i == 0
  (1 to Math.sqrt(n).toInt).view.collect {
    case i if nIsSquareOf(i) => 1
    case i if nHasFactor(i)  => 2
  }.sum
}

def runTestCases(f: Int => Int): Unit = {
  List(
    24 -> 8,
    1 -> 1,
    2 -> 2,
    3 -> 2,
    4 -> 3,
    5 -> 2,
    6 -> 4,
    36 -> 9,
    1020 -> 24,
    Int.MaxValue -> 2
  ).foreach {
    case (n, expectedCountOfFactors) =>
      val countedFactors = f(n)
      assert(
        countedFactors == expectedCountOfFactors,
        s"Expected number of factors of ${n} to be ${expectedCountOfFactors}, got ${countedFactors}"
      )
  }
}

runTestCases(countDivisorsFor)

Explanation

The most straightforward approach is to check from \(1\) all the way up to \(n\) and count number of times \(n\) is divisible in that range (and also check for squares). This has complexity \(O(n)\). But we can do better, because there is no larger factor than \(\sqrt{n}\), which means we can lower complexity to \(O(\sqrt{n})\).

If a number is not a square, then every divisor under a square root has a corresponding divisor above the square root - meaning we count it twice. If a number is square, this rule applies to every number except the square root - in which case, we count it only once.

What is the (1 to n).view syntax?

It is a combination of a Range and a "view", which creates a structure that does not evaluate until "forced" by an eager operation like .count. This reduces the number of intermediate allocations like those of an Array or a List type.

What is .collect?

From the Scala documentation on Range#collect,

Collect allows you to filter inputs and produce results after filtering in one go, allowing for much more concise syntax.