 # Ric0chet's solution

## to Prime Factors in the Scala Track

Published at Oct 03 2019 · 1 comment
Instructions
Test suite
Solution

Compute the prime factors of a given natural number.

A prime number is only evenly divisible by itself and 1.

Note that 1 is not a prime number.

## Example

What are the prime factors of 60?

• Our first divisor is 2. 2 goes into 60, leaving 30.
• 2 goes into 30, leaving 15.
• 2 doesn't go cleanly into 15. So let's move on to our next divisor, 3.
• 3 goes cleanly into 15, leaving 5.
• 3 does not go cleanly into 5. The next possible factor is 4.
• 4 does not go cleanly into 5. The next possible factor is 5.
• 5 does go cleanly into 5.
• We're left only with 1, so now, we're done.

Our successful divisors in that computation represent the list of prime factors of 60: 2, 2, 3, and 5.

You can check this yourself:

• 2 * 2 * 3 * 5
• = 4 * 15
• = 60
• Success!

The Scala exercises assume an SBT project scheme. The exercise solution source should be placed within the exercise directory/src/main/scala. The exercise unit tests can be found within the exercise directory/src/test/scala.

To run the tests simply run the command `sbt test` in the exercise directory.

Please see the learning and installation pages if you need any help.

## Source

The Prime Factors Kata by Uncle Bob http://butunclebob.com/ArticleS.UncleBob.ThePrimeFactorsKata

## Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

### PrimefactorsTest.scala

``````import org.scalatest.{Matchers, FunSuite}

/** @version 1.1.0 */
class PrimeFactorsTest extends FunSuite with Matchers {

test("no factors") {
PrimeFactors.factors(1) should be(List())
}

test("prime number") {
pending
PrimeFactors.factors(2) should be(List(2))
}

test("square of a prime") {
pending
PrimeFactors.factors(9) should be(List(3, 3))
}

test("cube of a prime") {
pending
PrimeFactors.factors(8) should be(List(2, 2, 2))
}

test("product of primes and non-primes") {
pending
PrimeFactors.factors(12) should be(List(2, 2, 3))
}

test("product of primes") {
pending
PrimeFactors.factors(901255) should be(List(5, 17, 23, 461))
}

test("factors include a large prime") {
pending
PrimeFactors.factors(93819012551l) should be(List(11, 9539, 894119))
}
}``````
``````import scala.collection.mutable.ListBuffer
//  10-03-19

object PrimeFactors {
def factors(num: Long): List[Long] = findPrimes(num)

// 41 ms -- FASTEST recursion matching divisor
//          (div :: acc & reverse  is faster than:  acc += div)
@annotation.tailrec
private def findPrimes(num: Long,
div: Long = 2,
acc: List[Long] = List()): List[Long] =
div match {
case d if num % d == 0L =>
findPrimes(num / div, div, div :: acc)
case d if d >= num => acc.reverse
case _ => findPrimes(num, div + 1, acc)
}

// 57 ms -- SLOWER recursion matching number
@annotation.tailrec
private def findPrimes2(num: Long,
div: Long = 2,
acc: List[Long] = List()): List[Long] =
num match {
case 1 => acc.reverse
case n if n % div == 0L =>
findPrimes2(num / div, div, div :: acc)
case _ => findPrimes2(num, div + 1, acc)
}

// 43 ms -- FAST brute-force using match case
private def findPrimes2(num: Long): List[Long] = {
if (num < 2) return List()

var facts = ListBuffer[Long]()
var n = num
var fact = 2L

while (fact * fact <= n) fact match {  // magic shortcut
case f if n % f == 0L =>
facts += fact
n /= fact
case f if f == 2L => fact += 1
case _ => fact += 2       // odds, only
}
if (n != 1L) facts += n     // prime remainder

facts.toList
}

// 43 ms -- FAST brute-force using nested while loops
private def findPrimes3(num: Long): List[Long] = {
if (num < 2) return List()

var facts = ListBuffer[Long]()
var n = num
var fact = 2L

while (fact * fact <= n) {  // magic shortcut
while (n % fact == 0L) {
facts += fact
n /= fact
}
fact += 1                 // odds & evens
}
if (n != 1L) facts += n     // prime remainder

facts.toList
}
}`````` I also proved to my own satisfaction that using: `div :: acc` (in L19, L32) plus `acc.reverse` (in L20, L30) has less overhead than: `acc += div` & plain `acc`