Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import cats.Order
import cats.collections.PairingHeap
import cats.instances.long._
import PairingHeap.empty
type Longs = Stream[Long]
implicit val x: Order[Longs] = (x, y) => x.head compare y.head
def spin(start: Long, wheel: Longs): Longs = {
def cycle(ns: Longs): Longs = ns append cycle(ns)
cycle(wheel).scan(start)(_ + _)
}
def toComposites(ns: Longs): Longs = {
def loop(m: Long, ms: Longs): Longs = (m * ms.head) #:: loop(m, ms.tail)
loop(ns.head, ns)
}
def sieve(candidates: Longs, composites: PairingHeap[Longs]): Longs =
candidates match { case n #:: ns =>
composites.minimumOption.fold {
n #:: sieve(ns, PairingHeap(toComposites(candidates)))
} { case m #:: ms =>
if (n < m) n #:: sieve(ns, composites + toComposites(candidates))
else sieve(if (m == n) ns else candidates, composites.remove + ms)
}
}
def primes: Longs = {
val startingPrimes = Stream(2L, 3L, 5L)
val wheel = Stream(4L, 2L, 4L, 2L, 4L, 6L, 2L, 6L)
sieve(startingPrimes.append(spin(7, wheel)), empty)
}
val criteria = List(
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,
167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251,
257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541)
assert(criteria == primes.take(100).toList)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment