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

?

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.