# 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:

• On Codility: CountFactors - Count factors of given number n.

## 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?

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