Sha256: d8e27f6964c74ead205ededcf08270a145276e6cdd828c6018ee5bdabfda4196

Contents?: true

Size: 599 Bytes

Versions: 176

Compression:

Stored size: 599 Bytes

Contents

import scala.annotation.tailrec

// Algorithm from - http://fldit-www.cs.uni-dortmund.de/~peter/PS07/HR.pdf
object PrimeFactors {
  def factors(n: Long): List[Long] = {
    assert(n >= 1, "Argument must be positive")

    @tailrec
    def primeAcc(n: Long, xs: List[Long]): List[Long] = {
      if (n == 1) xs
      else {
        val p = ld(n)
        primeAcc(n / p, p :: xs)
      }
    }

    primeAcc(n, List()).reverse
  }

  private def ld(n: Long) = ldf(2, n)

  @tailrec
  private def ldf(k: Long, n: Long): Long =
    if (n % k == 0) k
    else if (k * k > n) n
    else ldf(k + 1, n)
}


Version data entries

176 entries across 176 versions & 1 rubygems

Version Path
trackler-2.2.1.180 tracks/scala/exercises/prime-factors/example.scala
trackler-2.2.1.179 tracks/scala/exercises/prime-factors/example.scala
trackler-2.2.1.178 tracks/scala/exercises/prime-factors/example.scala
trackler-2.2.1.177 tracks/scala/exercises/prime-factors/example.scala
trackler-2.2.1.176 tracks/scala/exercises/prime-factors/example.scala
trackler-2.2.1.175 tracks/scala/exercises/prime-factors/example.scala
trackler-2.2.1.174 tracks/scala/exercises/prime-factors/example.scala
trackler-2.2.1.173 tracks/scala/exercises/prime-factors/example.scala
trackler-2.2.1.172 tracks/scala/exercises/prime-factors/example.scala
trackler-2.2.1.171 tracks/scala/exercises/prime-factors/example.scala
trackler-2.2.1.170 tracks/scala/exercises/prime-factors/example.scala
trackler-2.2.1.169 tracks/scala/exercises/prime-factors/example.scala
trackler-2.2.1.167 tracks/scala/exercises/prime-factors/example.scala
trackler-2.2.1.166 tracks/scala/exercises/prime-factors/example.scala
trackler-2.2.1.165 tracks/scala/exercises/prime-factors/example.scala
trackler-2.2.1.164 tracks/scala/exercises/prime-factors/example.scala
trackler-2.2.1.163 tracks/scala/exercises/prime-factors/example.scala
trackler-2.2.1.162 tracks/scala/exercises/prime-factors/example.scala
trackler-2.2.1.161 tracks/scala/exercises/prime-factors/example.scala
trackler-2.2.1.160 tracks/scala/exercises/prime-factors/example.scala