Skip to content

Instantly share code, notes, and snippets.

@mayonesa
Last active February 4, 2022 17:23
Show Gist options
  • Save mayonesa/521ceec41aaf48e0d35fc6be5dbfe9eb to your computer and use it in GitHub Desktop.
Save mayonesa/521ceec41aaf48e0d35fc6be5dbfe9eb to your computer and use it in GitHub Desktop.
Prime and count
// 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)
}
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)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment