Infinite (memoized) Prime Sequence in Kotlin

InfiniteSequence.kt

/**
 * This is an infinite prime sequence that's memoized in a linked list.
 *
 * Why? ... because I wanted to see what Kotlin is like. And who doesn't like prime numbers.
 */


import kotlin.system.measureTimeMillis

object Primes : Sequence<Long> {

    data class Node(
        val prime: Long,
        var next:  Node? = null
    )

    // Linked list that remembers already calculated primes
    val root = Node(2, next = Node(3, next = Node(5)))


    override fun iterator() = PrimeIterator()

    class PrimeIterator: Iterator<Long> {

        var cur = Primes.root

        override fun hasNext() = true

        override fun next(): Long {

            val prev = cur
            cur = cur.next ?: nextPrimeAfter(prev.prime + 1)
            prev.next = cur

            return prev.prime
        }

        fun nextPrimeAfter(x: Long): Node = when {
            Primes.anyDivide(x) -> nextPrimeAfter(x + 1)
            else                -> Node(x)
        }

    }

}

fun Sequence<Long>.anyDivide(x: Long) = this.takeWhile { (it*it) <= x }.any { x % it == 0L }




/**
 * Here is a simple performance test to show that memoization works
 */

fun main(args: Array<String>) {

    // 1 mio. primes will eat up ~1.2GiB RAM
    val n = 1000000

    println("Summing first $n primes...\n")

    // takes 5-30s (depends on the computer's resources)
    val normalMS = measureTimeMillis {
        println("Sum (normal): ${Primes.take(n).sum()}")
    }

    println("Duration (normal): ${normalMS / 1000.0}s\n")

    // takes only 0.01s! because computations are remembered
    val memoizedMS = measureTimeMillis {
        println("Sum (memoized): ${Primes.take(n).sum()}")
    }

    println("Duration (memoized): ${memoizedMS / 1000.0}s")

}