Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 15 стр.

                                                                       16

его делителей. Будем использовать обозначение bxc для функции floor(x),
равной наибольшему целому числу, не превышающему x (округление вниз).
Аналогично, dxe используется для обозначения функции ceil(x), равной
наименьшему целому числу, большему или равному x (округление вверх).
       Для этого в цикле выполняется пробное деление n на все целые числа
        √
от 2 до n:

         int Tr_div(int n)
         {
                             √
         for(int i = 2; i < b nc; i + +)
         if (n%i == 0) return i;
         return 0}

        Каждое деление имеет асимптотическую сложность O(log 2 n), поэтому
общая сложность метода может быть оценена как O(n1/2 log 2 n). Обозначим
через L длину двоичного представления числа n, L = dlog2 ne. Тогда можно
записать последнюю оценку в более стандартном для теории вычислимости
виде:
              T (n) = O(L2 · eL/2 ).                                 (1.2)

        Значит, алгоритм пробных делений имеет экспоненциальную оценку
относительно длины входного числа, поэтому этот метод не может быть
использован для тестирования больших чисел.


1.5. Решето Аткина
        Решето Аткина — быстрый современный алгоритм нахождения всех
простых чисел до заданного целого числа. Это оптимизированная версия
старинного решета Эратосфена: решето Аткина проделывает некоторую
предварительную работу, а затем вычеркивает числа, кратные квадрату
простых. Алгоритм был создан А. Аткиным (A. Atkin) и Д. Бернштейном
(D. Bernstein).
        Ниже представлена упрощенная версия кода, иллюстрирующая
основную идею алгоритма – использование квадратичных форм.