public
Created

Simple prime number utilities

  • Download Gist
Primes.scala
Scala
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
// 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)
}
}
Primes2.scala
Scala
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
// 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 }
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.