Skip to content

Instantly share code, notes, and snippets.

@domnikl
Last active June 19, 2024 08:25
Show Gist options
  • Save domnikl/6ad30f0a6ca3228f44e8273c08dbd879 to your computer and use it in GitHub Desktop.
Save domnikl/6ad30f0a6ca3228f44e8273c08dbd879 to your computer and use it in GitHub Desktop.
Kotlin Prime number sequence
fun primes(): Sequence<Long> {
var i = 0L
return sequence {
generateSequence { i++ }
.filter { n -> n > 1 && ((2 until n).none { i -> n % i == 0L }) }
.forEach { yield(it) }
}
}
println(primes().take(10).joinToString(", "))
@GregorBlock
Copy link

Thanks, I have modified it a bit to work faster with larger prime numbers.

fun primes2(): Sequence<Long> {
    var i = 2L
    return sequence {
        generateSequence { i++ }
                .filter { n ->
                    when {
                        n == 1L -> false
                        n < 4 -> true
                        n.rem(2) == 0L -> false
                        n < 9 -> true
                        n.rem(3) == 0L -> false
                        else -> {
                            val r = floor(sqrt(n.toDouble()))
                            var f = 5
                            while (f <= r) {
                                if (n.rem(f) == 0L || n.rem(f + 2) == 0L) return@filter false
                                f += 6
                            }
                            true
                        }
                    }
                }
                .forEach { yield(it) }
    }
}

@domnikl
Copy link
Author

domnikl commented Dec 30, 2019

Hey, looks great, thanks for sharing it!

@mirianfonkam
Copy link

This is really cool! I learned something new with generateSequence.

Preserving behavior of primes.kts I would simplify as:

fun primes() = generateSequence(seed = 2L) { prevValue ->
    prevValue + 1L
}.filter { candidate ->
    ((2 until candidate).none { i -> candidate % i == 0L })
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment