I have implemented the Sieve of Eratosthenes in Kotlin to generate prime numbers. I noticed an issue where the second version of my code does not work correctly, and I'm puzzled as to why the number 4 is missing in the output.
Here is the code that works correctly:
val primes: Sequence<Int> = sequence {
var numbers = generateSequence(2) { it + 1 }
Log.d("testsss", "Initial numbers: ${numbers.take(10).toList()}") // Initial numbers
while (true) {
val prime = numbers.first()
Log.d("testsss", "Current prime: $prime")
yield(prime)
numbers = numbers.drop(1).filter { it % prime != 0 }
Log.d("testsss", "After filtering with prime $prime: ${numbers.take(10).toList()}") // After filtering
}
}
val primesList = primes.take(10).toList()
Log.d("testsss", "Final primes: $primesList")
println(primesList)
The logs for the working code are as follows:
Initial numbers: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Current prime: 2
After filtering with prime 2: [3, 5, 7, 9, 11, 13, 15, 17, 19, 21]
Current prime: 3
After filtering with prime 3: [5, 7, 11, 13, 17, 19, 23, 25, 29, 31]
Current prime: 5
After filtering with prime 5: [7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
Current prime: 7
After filtering with prime 7: [11, 13, 17, 19, 23, 29, 31, 37, 41, 43]
Current prime: 11
After filtering with prime 11: [13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
Current prime: 13
After filtering with prime 13: [17, 19, 23, 29, 31, 37, 41, 43, 47, 53]
Current prime: 17
After filtering with prime 17: [19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
Current prime: 19
After filtering with prime 19: [23, 29, 31, 37, 41, 43, 47, 53, 59, 61]
Current prime: 23
After filtering with prime 23: [29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
Current prime: 29
Final primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Now, here is the code that does not work correctly:
val primes: Sequence<Int> = sequence {
var numbers = generateSequence(2) { it + 1 }
Log.d("testsss", "Initial numbers: ${numbers.take(10).toList()}") // Initial numbers
var prime: Int
while (true) {
prime = numbers.first()
Log.d("testsss", "Current prime: $prime")
yield(prime)
numbers = numbers.drop(1).filter { it % prime != 0 }
Log.d("testsss", "After filtering with prime $prime: ${numbers.take(10).toList()}") // After filtering
}
}
val primesList = primes.take(10).toList()
Log.d("testsss", "Final primes: $primesList")
println(primesList)
The logs for the problematic code are:
Initial numbers: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Current prime: 2
After filtering with prime 2: [3, 5, 7, 9, 11, 13, 15, 17, 19, 21]
Current prime: 3
After filtering with prime 3: [5, 7, 8, 10, 11, 13, 14, 16, 17, 19]
Current prime: 5
After filtering with prime 5: [6, 7, 8, 9, 11, 12, 13, 14, 16, 17]
Current prime: 6
After filtering with prime 6: [7, 8, 9, 10, 11, 13, 14, 15, 16, 17]
Current prime: 7
After filtering with prime 7: [8, 9, 10, 11, 12, 13, 15, 16, 17, 18]
Current prime: 8
After filtering with prime 8: [9, 10, 11, 12, 13, 14, 15, 17, 18, 19]
Current prime: 9
After filtering with prime 9: [10, 11, 12, 13, 14, 15, 16, 17, 19, 20]
Current prime: 10
After filtering with prime 10: [11, 12, 13, 14, 15, 16, 17, 18, 19, 21]
Current prime: 11
After filtering with prime 11: [12, 13, 14, 15, 16, 17, 18, 19, 20, 21]
Current prime: 12
Final primes: [2, 3, 5, 6, 7, 8, 9, 10, 11, 12]
I understand that due to the lazy evaluation of Kotlin sequences, the filter part is referencing the wrong prime values. However, if lazy evaluation of the filter happens for all primes, then 4 should appear. If the filter was applied correctly for prime = 2, subsequent multiples of 2 like 6, 8, 10, and 12 should not appear in the results. What mistake might I be making in my understanding?
The problem is here:
numbers.drop(1).filter { it % prime != 0 }
The lambda (the expression in curly braces) is executed only when a terminal operator is applied to the sequence, i.e. first() called on the next iteration of the while loop. In order for Kotlin to later execute a lambda it captures all variables that are used. In this case that is prime. Note: The variable is captured, not the value of the variable.
For each iteration of the while loop another filter is applied (i.e. for each prime). So there are multiple lambdas, each capturing prime. That is the same variable for all captures, though. When all filters are executed, they all use the current state of prime, so they will all filter on the same value:
At the start of the third iteration prime is 3 and first() is called. Now all filters are executed. There are currently two filters on numbers:
filter { it % prime != 0 }
filter { it % prime != 0 }
The first was applied when prime was 2, the second when it was 3. That doesn't matter, though, because the current value of prime is taken, not what it was when the filter was defined. And that value is now 3. So the same filter is executed twice and the intended filter for it % 2 doesn't occur so 4 is never filtered.
That is different in your first example: Each iteration of the while loop has its own prime variable, so the capture of the filter's lambda captures a different variable each time that will never change. When the multiple filters are eventually executed they each use their own prime variable, so they will each filter on a different value, resulting in the expected output.