Kotlin sieve using sequences

Question

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)}") } }

Pavel · Accepted Answer · 2020-03-29 18:47:45Z

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")

Start with the first element in the sequence - number 2
Filter out all numbers divisible by 2
Yield 2
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...

Stack Exchange Network

Kotlin sieve using sequences

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Kotlin sieve using sequences

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions