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

}

</source>

К.Королев

О соотношении Сундарама

используется как решето простых чисел по принципу «как есть» и это соотношение действительно есть

готовый оператор для любого языка программирования высокого уровня. Однако, если рассматривать это

3-го тома. Приведенное в ответе, цитата, «решение несколько замысловато: в нем пропускаются все

числа, кратные 3». Решение предложено Б.Чартресом.

все числа, кратные 3. Вернее, с точки зрения матрицы (1) этот алгоритм пропускает все строки

и столбцы матрицы, кратные 3-м. Приведем этот алгоритм, реализованный на ассемблере. Смысл

используемых переменных следующий:

число вычисляется как 2J+1. Понятно, что отсутствует элемент массива, соответствующий

тривиальной двойке.

 

SS_33-процедура с исключением строк и столбцов, «кратных» 3-ем

;Решето Сундарама: отсеивание из последовательности нечетных чисел всех составных чисел.

;Инициализация массива Prime, нулевой элемент которого, соответствующий

mov Byte Ptr Prime[eax],0 ; последнее нечетное число составное

@@End:

 

Приведенный алгоритм работает в 3-4 раза быстрее (по времени), например, алгоритма Аткина-Бернстейна.

исключающие дополнительно строки, «кратные» 5-ти и 7-ми соответственно, но они имеют еще большее

преимущество.

Кстати, это не единственный результат, который можно получить из (1). Так, за 15-20 минут из (1)

невозможно не получить бинарный алгоритм вычисления НОД (наибольшего общего делителя).

[[Категория:Программирование]]