Prime and count

Prime.scala

// prime: cannot be divided by any number other than itself and 1                //import cats.data.State
trait Prime0 {
  def isPrime(n: Int): Boolean
  def countPrimes(n: Int): (Int, Prime0)                                          //trait Prime
}

object Prime0 extends App {
  private val InitPrimeCount = Seq(0, 0, 1, 2)
  //object Prime
  def apply(): Prime0 = new PrimeImpl(InitPrimeCount)

  private class PrimeImpl(cache0: Seq[Int]) extends Prime0 {
    override def isPrime(n: Int): Boolean = (2 until n).forall(n % _ != 0)

    override def countPrimes(n0: Int): (Int, Prime0) = {
      val maxN = cache0.size - 1
      if (n0 <= maxN) {
        (cache0(n0), this)
      } else {
        val maxCount = cache0.last
        val (countR, cacheR) = (maxN + 1 to n0).foldLeft((maxCount, cache0)) { case ((acc, cache), n) =>
          val count = if (isPrime(n)) acc + 1 else acc
          (count, cache :+ count)
        }
        (countR, new PrimeImpl(cacheR))
      }
    }
  }

  val (count0, prime0) = Prime0().countPrimes(10000)
  println(count0)
  println(prime0.countPrimes(9999)._1)
  val (count1, prime1) = prime0.countPrimes(100000)
  println(count1)
  println(prime1.countPrimes(100001)._1)
}

PrimeState.scala

import cats.data.State

// prime: cannot be divided by any number other than itself and 1
object Prime extends App {
  private val InitPrimeCount = Seq(0, 0)

  def isPrime(n: Int): Boolean = (2 until n).forall(n % _ != 0)

  def countPrimes(n0: Int): State[Seq[Int], Int] =
    State { cache0 =>
      val maxN = cache0.size - 1
      if (n0 <= maxN) {
        (cache0, cache0(n0))
      } else {
        val maxCount = cache0.last
        (maxN + 1 to n0).foldLeft((cache0, maxCount)) { case ((cache, count0), n) =>
          val count = if (isPrime(n)) count0 + 1 else count0
          (cache :+ count, count)
        }
      }
    }

  val primeCounts = for {
    c1 <- countPrimes(0)
    c2 <- countPrimes(1)
    c3 <- countPrimes(2)
    c4 <- countPrimes(9000)
    c5 <- countPrimes(100000)
  } yield (c1, c2, c3, c4, c5)

  println(primeCounts.runA(InitPrimeCount).value)
}