Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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 }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.