Проблемы реализации сита Эратосфена в Котлине — почему отсутствует 4?

Я реализовал Решето Эратосфена в Котлине для генерации простых чисел. Я заметил проблему, из-за которой вторая версия моего кода работает неправильно, и недоумеваю, почему в выводе отсутствует цифра 4.

Вот код, который работает правильно:

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)

Логи рабочего кода следующие:

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]

Теперь вот код, который работает неправильно:

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)

Журналы проблемного кода:

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]

Я понимаю, что из-за ленивой оценки последовательностей Kotlin часть фильтра ссылается на неправильные простые значения. Однако если ленивая оценка фильтра происходит для всех простых чисел, то должно появиться 4. Если фильтр был применен правильно для простого числа = 2, последующие числа, кратные 2, например 6, 8, 10 и 12, не должны появляться в результатах. Какую ошибку я могу допустить в своем понимании?

2
0
51
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Проблема здесь:

numbers.drop(1).filter { it % prime != 0 }

Лямбда (выражение в фигурных скобках) выполняется только тогда, когда к последовательности применяется оператор терминала, т. е. first() вызывается на следующей итерации цикла while. Чтобы впоследствии Kotlin мог выполнить лямбду, он фиксирует все используемые переменные. В данном случае это prime. Примечание. Записывается переменная, а не ее значение.

Для каждой итерации цикла while применяется еще один filter (т. е. для каждого простого числа). Итак, существует несколько лямбд, каждая из которых захватывает prime. Однако это одна и та же переменная для всех захватов. Когда все фильтры выполняются, все они используют текущее состояние prime, поэтому все они будут фильтровать одно и то же значение:

В начале третьей итерации prime вызывается 3 и first(). Теперь все фильтры выполнены. На данный момент на numbers есть два фильтра:

filter { it % prime != 0 }
filter { it % prime != 0 }

Первый применялся, когда prime было 2, второй — когда 3. Однако это не имеет значения, поскольку берется текущее значение prime, а не то, которое было при определении фильтра. И эта ценность сейчас 3. Таким образом, один и тот же фильтр выполняется дважды, а предполагаемый фильтр для it % 2 не возникает, поэтому 4 никогда не фильтруется.

В вашем первом примере все по-другому: каждая итерация цикла while имеет свою собственную переменную prime, поэтому захват лямбды фильтра каждый раз фиксирует другую переменную, которая никогда не изменится. Когда в конечном итоге выполняются несколько фильтров, каждый из них использует свою собственную переменную prime, поэтому каждый из них будет фильтровать свое значение, что приведет к ожидаемому результату.

Спасибо за ваш ценный ответ. Поскольку я не очень хорошо владею английским языком, я воспользовался переводчиком как для своего вопроса, так и для этого комментария. Приношу извинения за возможные недостатки и прошу вашего понимания. Основываясь на вашей идее, вы упомянули, что фильтрация работает правильно, начиная с того момента, когда простое число равно 3. Однако, когда я рассчитал следующие шаги, все кажется другим: [первые] числа: 2, 3, 4, 5, 6, 7, 8 , 9, 10, 11 простые числа: 2 После удаления 2: числа: 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 Фильтр с простым числом = 2 не работает (из-за ленивой оценки)

JSW 28.06.2024 17:47

[вторые] числа: 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 простые числа: 2, 3 После отбрасывания 3: числа: 4, 5, 6, 7, 8, 9, 10, 11 , 12, 13 Фильтр с простым = 3: числа: 4, 5, 7, 8, 10, 11, 13, 14, 16, 17 [третьи] числа: 4, 5, 7, 8, 10, 11, 13, 14, 16, 17 простых чисел: 2, 3, 4??????? Следуя этой логике, простые числа будут включать 4, что противоречит окончательным неправильным выводам 2, 3, 5, 6, 7, 8, 9, 10, 11, 12. Где может быть ошибка? Есть ли ошибка в моих расчетах или я неправильно понял ваше объяснение? Спасибо!

JSW 28.06.2024 17:48

Другие вопросы по теме