Реализации алгоритмов/Решето Сундарама: различия между версиями

используется как решето простых чисел по принципу «как есть» и это соотношение действительно есть готовый оператор для любого языка программирования высокого уровня. Однако, если рассматривать это соотношение как симметричную матрицу, то решето можно реализовать более эффективно. Но сначала обратимся ко 2-му тому культовой монографии Д.Кнута «Искусство программирования», точнее, к упр.8 раздела 4.5.4. «Разложение на простые множители». В упражнении предлагается найти алгоритм высеивания, использующий только операции сложения и вычитания, а в ответе на него приведены соотношения, непосредственно вытекающие из (1): в оригинальных обозначениях монографии это p = 2j + 1 и q = 2j + 2j22j² соответственно. Сам же Д.Кнут происхождение этих выражений не объясняет, возможно, по причине весьма скромного рейтинга упражнения (задача на 15 – 20 минут), которое имеет, хотя тематически и не совсем логичное, продолжение в упражнении 15 раздела 5.2.3 3-го тома. Приведенное в ответе, цитата, «решение несколько замысловато: в нем пропускаются все числа, кратные 3». Решение предложено Б.Чартресом.