Instantly share code, notes, and snippets.

jesperdj/Primes.scala Created Mar 14, 2012

Simple prime number utilities
 // Simple prime number utilities object Primes { private val buffer = scala.collection.mutable.ArrayBuffer(2) // Given the primes ps, check if x is a prime by trial division private def check(ps: Traversable[Int])(x: Int) = { val limit = math.sqrt(x).ceil.toInt ps takeWhile { _ <= limit } forall { x % _ != 0 } } // Get the i'th prime; store primes found so far in the buffer private def get(i: Int) = { while (buffer.length <= i) buffer += (Stream.from(buffer.last + 1) find check(buffer) get) buffer(i) } val stream = { def s(i: Int): Stream[Int] = get(i) #:: s(i + 1); s(0) } val isPrime: PartialFunction[Int, Boolean] = { case 2 => true case x if x > 2 => check(stream)(x) } def factorize(x: Int): Stream[Int] = { val factor = { val limit = math.sqrt(x).ceil.toInt stream takeWhile { _ <= limit } find { x % _ == 0 } getOrElse x } val rest = x / factor factor #:: (if (rest > 1) factorize(rest) else Stream.empty) } }
 // A shorter version that doesn't contain a mutable buffer object Primes2 { val stream = 2 #:: 3 #:: 5 #:: primesFrom(7) def primesFrom(x: Int): Stream[Int] = if (isPrime(x)) x #:: primesFrom(x + 1) else primesFrom(x + 1) val isPrime: PartialFunction[Int, Boolean] = { case 2 => true case x if x > 2 => val limit = math.sqrt(x).ceil.toInt; stream takeWhile { _ <= limit } forall { x % _ != 0 } } def factorize(x: Int): Stream[Int] = { val f = { val limit = math.sqrt(x).ceil.toInt; stream takeWhile { _ <= limit } find { x % _ == 0 } getOrElse x } f #:: { val r = x / f; if (r == 1) Stream.empty else factorize(r) } } def almostPrimes(n: Int): Stream[Int] = Stream.from(4) filter { factorize(_).length == n } }
to join this conversation on GitHub. Already have an account? Sign in to comment