6
\$\begingroup\$

While learning about functional programming the simple sieve example was brought up in Haskell. I wanted to try a Kotlin implementation using sequences.

Are there any other quick wins without modifying the structure too much?

import kotlin.coroutines.experimental.buildSequence
import kotlin.system.measureTimeMillis

fun sieve(isPrime: Int, ints: Sequence<Int>): Boolean = with(ints.first()){
    return when {
        isPrime  < 2 -> false
        isPrime == 2 -> true
        isPrime == this -> true
        isPrime.rem(2) == 0 -> false
//        isPrime.and(1) == 0 -> false // same way to check if number is even
        this > isPrime -> false
        else -> sieve(isPrime, ints.filter { n -> n.rem(this) != 0 })
    }
}

fun main(args: Array<String>) {
    val lazySeq = buildSequence { for (i in 3..Int.MAX_VALUE step 2) yield(i) }
    println("Duration = ${measureTimeMillis { println("isPrime(4057) = ${sieve(4057, lazySeq)}") }}ms")
//    (2..200).forEach { println("isPrime($it) = ${sieve(it, lazySeq)}") }
}
\$\endgroup\$
2
\$\begingroup\$

Here's my take on this:

import kotlin.system.measureTimeMillis

fun sieve(xs: Sequence<Int>): Sequence<Int> = sequence {
    val head = xs.first()
    val tail = xs.drop(1).filter { it % head != 0 }
    yield(head)
    for (i in sieve(tail))
        yield(i)
}

val primes = sieve(generateSequence(2) { it + 1 })
fun isPrime(n: Int) = primes.contains(n)

val durationMs = measureTimeMillis {
    println("isPrime(4057) = ${isPrime(4057)}")
}
println("Duration = $durationMs ms")
  1. Start with the first element in the sequence - number 2
  2. Filter out all numbers divisible by 2
  3. Yield 2
  4. Yield the rest recursively:
    1. Start with the first element in the sequence - number 3
    2. Filter out all numbers divisible by 3
    3. Yield 3
    4. Yield the rest recursively...
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.