Postponed Prime Sequence in Kotlin

Following my previous unbounded prime generator and a followup by Martin R, I've tested the waters in Kotlin by making an unbounded sieve.

To quote Martin R's wonderful explanation of the base algorithm,


The interesting thing about that algorithm is that the prime generator needs a list of "base primes" which are created using another instance of itself. This works because

• the base prime generator is created "delayed", after producing some fixed primes, and

• in order to generate primes up to \$ N \$, base primes are needed only up to \$ \sqrt N \$

so that the creation of nested prime generators terminates eventually.


The sieving is done using a dictionary which holds the "next composite numbers" which are divisible by any prime less than the current base prime. As explained [on SO], the required memory to produce \$ n \$ primes is \$ O(\sqrt n). \$

class PostponedPrimeSequence() : AbstractIterator(), Sequence {
override fun iterator() = this

private var basePrimes: PostponedPrimeSequence? = null
private var basePrime = 0

private var sieve = mutableMapOf()
private var initialPrimes = mutableListOf(2, 3, 5, 7)
private var candidate = 9

override fun computeNext() {
if (!initialPrimes.isEmpty()) {
setNext(initialPrimes.removeAt(0))
} else {
if (candidate == 9) {
basePrimes = PostponedPrimeSequence()
basePrimes!!.next()
basePrime = basePrimes!!.next()
assert(candidate == basePrime * basePrime)
}

while (candidate > 0) {
val factor = sieve.remove(candidate) ?:
if (candidate == basePrime * basePrime) {
val temp = basePrime
basePrime = basePrimes!!.next()
temp
} else {
assert(candidate

Usage:

PostponedPri

• You can make basePrimes a lateinit non-null var to avoid !!.

• sieve and initialPrimes are only assigned once so they can be marked with val instead of var

• sequenceOf(2, 3, 4, 7).iterator() can be used along with Iterator.hasNext and Iterator.next instead of mutableListOf(2, 3, 5, 7) with somewhat difficult to read !initialPrimes.isEmpty() and initialPrimes.removeAt(0) (although if you really prefer to use a collection instead of an iterator then you can use isNotEmpty instead of !collection.isEmpty).

• Instead of explicitly declaring a temp variable you can use apply to take the current value of a variable, use/change it, and return the initial value.

• As an alternative to sieve.containsKey(j) you can use j in sieve.

• As an alternative to candidate += 2 } candidate += 2 you can move the latter += 2 to relatively the beginning of computeNext (requires a few other changes, see below). The name candidate would no longer really fit though, but I think a generic property name like value is sufficient enough (we know what "value" we care about so we know what we're computing as we go, etc.).

• You probably shouldn't implement Iterator and Sequence in the same object. e.g. When invoking with(PostponedPrimeSequence()) { repeat(2) { take(20).forEach(::println) } } I would expect it as a Sequence to print the first 20 primes twice (or throw "IllegalStateException: This sequence can be consumed only once.") but as an Iterator I would expect it to print the first 40 primes. These are conflicting expectations. I recommend only implementing one. A Sequence is understood to possibly be constrained to be iterated only once so I would implement the base Iterator and then wrap it as a Sequence in a top-level function for convenience.

e.g.

fun generatePrimeSequence() = PostponedPrimeIterator().asSequence()

class PostponedPrimeIterator() : AbstractIterator() {
    private lateinit var basePrimes: PostponedPrimeIterator
    private var basePrime = 0

    private val sieve = mutableMapOf()
    private val initialPrimes = sequenceOf(2, 3, 5, 7).iterator()
    private var value = 0

    override fun computeNext() {
        if (initialPrimes.hasNext()) {
            value = initialPrimes.next()
            setNext(value)
        } else {
            value += 2

            if (value == 9) {
                basePrimes = PostponedPrimeIterator()
                basePrimes.next()
                basePrime = basePrimes.next()
                assert(value == basePrime * basePrime)
            }

            while (value > 0) {
                val factor = sieve.remove(value) ?:
                        if (value == basePrime * basePrime) {
                            basePrime.apply {
                                basePrime = basePrimes.next()
                            }
                        } else {
                            assert(value < basePrime * basePrime)
                            setNext(value)
                            break
                        }
                var j = value + 2 * factor
                while (j in sieve) {
                    j += 2 * factor
                }
                sieve[j] = factor
                value += 2
            }
        }
    }
}

Usage:

generatePrimeSequence().take(20).forEach(::println)

StackExchange Code Review Q#139635, answer score: 2