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

                                                                       29

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

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

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

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


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