Return to Question

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). \$

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). \$

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

• Naming: As I'm new to Kotlin, I don't know the naming conventions yet
• Performance: If there are simple, provable improvements without drastically changing the algorithm (such as adding a large wheel)
• Iteration organization: As Kotlin lacks a true yielding generator and I wanted a true Iterator/Sequence, rather than a callback based "poor man's yield", the iteration isn't exactly the prettiest matter. The candidate += 2 } candidate += 2 bit especially feels like there should be a better way to do this, and the break (which is related) breaks ^_ha simple control flow, which is not ideal.
• !!: Even on the line immediately following assignment to basePrimes, I have to use !! to potentially fail on accessing the next method (Smart cast to 'PostponedPrimeSequence' is impossible, because 'basePrimes' is a mutable property that could have been changed by this time). I know that, due to reflection, any variable on the JVM could change at any time, but this seems (削除) like a smelly smell that smells (削除ここまで) smelly. basePrimes has to be mutable and start out null, though, because otherwise the class would recursively take infinite space. In this case, though, I want to initialize it once, late, and from then on it should act as an immutable (non-nullable) val reference. If this is possible in Kotlin, I don't know how to do so yet.

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

• Naming: As I'm new to Kotlin, I don't know the naming conventions yet
• Performance: If there are simple, provable improvements without drastically changing the algorithm (such as adding a large wheel)
• Iteration organization: As Kotlin lacks a true yielding generator and I wanted a true Iterator/Sequence, rather than a callback based "poor man's yield", the iteration isn't exactly the prettiest matter. The candidate += 2 } candidate += 2 bit especially feels like there should be a better way to do this, and the break (which is related) breaks ^_ha simple control flow, which is not ideal.
• !!: Even on the line immediately following assignment to basePrimes, I have to use !! to potentially fail on accessing the next method (Smart cast to 'PostponedPrimeSequence' is impossible, because 'basePrimes' is a mutable property that could have been changed by this time). I know that, due to reflection, any variable on the JVM could change at any time, but this seems (削除) like a smelly smell that smells (削除ここまで) smelly. basePrimes has to be mutable and start out null, though, because otherwise the class would recursively take infinite space. In this case, though, I want to initialize it once, late, and from then on it should act as an immutable (non-nullable) val reference. If this is possible in Kotlin, I don't know how to do so yet.

class PostponedPrimeSequence() : AbstractIterator<Int>(), Sequence<Int> {
 override fun iterator() = this
 private var basePrimes: PostponedPrimeSequence? = null
 private var basePrime = 0
 private var sieve = mutableMapOf<Int, Int>()
 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 < basePrime * basePrime)
 setNext(candidate)
 break
 }
 var j = candidate + 2 * factor
 while (sieve.containsKey(j)) {
 j += 2 * factor
 }
 sieve[j] = factor
 candidate += 2
 }
 candidate += 2
 }
 }
}

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

class PostponedPrimeSequence() : AbstractIterator<Int>(), Sequence<Int> {
 override fun iterator() = this
 private var basePrimes: PostponedPrimeSequence? = null
 private var basePrime = 0
 private var sieve = mutableMapOf<Int, Int>()
 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 < basePrime * basePrime)
 setNext(candidate)
 break
 }
 var j = candidate + 2 * factor
 while (sieve.containsKey(j)) {
 j += 2 * factor
 }
 sieve[j] = factor
 candidate += 2
 }
 candidate += 2
 }
 }
}

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