Алгоритм простого деления
Алгоритмы формирования таблиц простых чисел
Цель работы Освоить современные методы и базовые алгоритмы формирования таблиц простых чисел.
Порядок выполнения работы 1. Повторить основные термины арифметики и теории чисел, связанные с понятиями простого, составного и взаимно-простого числа, разложением числа на множители, кратностью. 2. Провести поиск в Интернет и в литературных источниках, найти понятие и описание способов получения таблиц простых чисел. В качестве базовых предлагаются методы простого перебора (простого деления); алгоритмы Эратосфена; Сундарама и Аткина. Можно предложить иной современный или самостоятельно разработанный алгоритм. 3. Используя выбранный (по таблице вариантов или самостоятельно найденный) алгоритм, составить таблицу простых чисел для заданного интервала и подсчитать их количество. 3. Подготовить отчет, содержащий: 1) Титульный лист 2) Введение (о применении простых чисел в защите информации); 3) Основной раздел, в котором: - дать определения всем перечисленным в п.1 понятиям (простое число, составное число, число кратное заданному и т.д.); - словесно описать схему получения таблиц простых чисел выбранным методом; - составить алгоритм (отобразить блок-схему) формирования таблицы простых чисел для заданного интервала и подсчета количества таких чисел; - привести программу работы алгоритма (выбор языка - произвольный); - показать результаты работы программы, сформировать таблицу простых чисел в заданном интервале (от m до n) и подсчитать их количество; - определить количество операций сложения (вычитания) и умножения (деления) либо сдвига, необходимых для получения результата (вычислительную сложность метода), отразить в отчете. 4) Выводы.
Таблица 1. Варианты заданий
Алгоритмы поиска простых чисел (базовые сведения) Решето Эратосфена Вполне вероятно, что алгоритм, придуманный более 2000 лет назад греческим математиком Эратосфеном Киренским, был первым в своем роде. Его единственная задача – нахождение всех простых чисел до некоторого заданного числа N. Термин «решето» подразумевает фильтрацию, а именно фильтрацию всех чисел за исключением простых. Так, обработка алгоритмом числовой последовательности оставит лишь простые числа, все составные же отсеются. Рассмотрим в общих чертах работу метода. Дана упорядоченная по возрастанию последовательность натуральных чисел. Следуя методу Эратосфена, возьмем некоторое число P изначально равное 2 – первому простому числу, и вычеркнем из последовательности все числа кратные P: 2P, 3P, 4P, …, iP (iP≤N). Далее, из получившегося списка в качестве P берется следующее за двойкой число – тройка, вычеркиваются все кратные ей числа (6, 9, 12, …). По такому принципу алгоритм продолжает выполняться для оставшейся части последовательности, отсеивая все составные числа в заданном диапазоне.
В приведенной таблице записаны натуральные числа от 2 до 100. Красным помечены те, которые удаляются в процессе выполнения алгоритма «Решето Эратосфена». Программная реализация алгоритма Эратосфена потребует: 1. организовать логический массив и присвоить его элементам из диапазона от 2 до N логическую единицу; 2. в свободную переменную P записать число 2, являющееся первым простым числом; 3. исключить из массива все числа кратные P2, ступая с шагом по P; 4. записать в P следующее за ним не зачеркнутое число; 5. повторять действия, описанные в двух предыдущих пунктах, пока это возможно. Обратите внимание: на третьем шаге мы исключаем числа, начиная сразу с P2, это связано с тем, что все составные числа меньшие P будут уже зачеркнуты. Поэтому процесс фильтрации следует остановить, когда P2 станет превышать N. Это важное замечание позволяет улучшить алгоритм, уменьшив число выполняемых операций. Так будет выглядеть псевдокод алгоритма: P←2 { пока i≤N выполнять { Он состоит из двух циклов: внешнего и внутреннего. Внешний цикл выполняется до тех пор, пока P2 не превысит N. Само же P изменяется с шагом P+1. Внутренний цикл выполняется лишь в том случае, если на очередном шаге внешнего цикла окажется, что элемент с индексом P не зачеркнут. Именно во внутреннем цикле происходит отсеивание всех составных чисел. Решето Эратосфена для выявления всех простых чисел в заданной последовательности ограниченной некоторым N потребует O(Nlog (log N)) операций. Поэтому уместнее использовать данный метод чем, например, наиболее тривиальный и затратный перебор делителей.
Решето Сундарама Решето Сундарама – алгоритм поиска всех простых чисел в некотором заданном диапазоне. Он был разработан в 1934 году ныне безызвестным студентом из Индии С. П. Сундарамом. Принцип работы алгоритма Сундарама сводится, как и в его знаменитом предшественнике, к последовательному отсеиванию всех ненужных чисел. Но у него есть одна небольшая особенность: результатом работы алгоритма будет последовательность простых чисел из диапазона от 2 до удвоенного значения граничного числа. Допустим необходимо получить все простые числа до некоторого N, тогда выходными данными будут все простые числа от 2 до 2N+1. Решето Сундарама из ряда натуральных чисел, не превышающих N, исключает числа вида 2ij+i+j. Результат данного выражения, ни при каких значениях входящих в него переменных, не превышает N (2ij+i+j≤N). Соблюдая это условие, а также то, что i всегда меньше или равно j, переменные i и j пробегают все натуральные значения из множеств: После исключения всех ненужных чисел необходимо увеличить каждое оставшиеся число в два раза и прибавить единицу (2i+1). Итоговое множество будет содержать числа: 2, 3, …, 2N+1.
Решето Аткина. Описание алгоритма: Алгоритм состоит из следующих шагов. 1. Выписываются все натуральные числа из диапазона от 1 до n.
2. Перебираются все возможные пары чисел x, y, где x<=sqrt(n) и y<=sqrt(n). Т.е. (1,1), (1,2),…, (1,sqrt(n)), (2,1), (2,2),…, (sqrt(n),sqrt(n)). 3. Для каждой пары чисел вычисляются значения следующих трех уравнений: a) 4*x^2+y^2; b) 3*x^2+y^2; c) 3*x^2-y^2, значение вычисляется только при x>y. 4. Для каждого вычисленного значения уравнений вычисляются остатки от деления на 12, причем a) если остаток равен 1 или 5 для значения первого уравнения; b) если остаток равен 7 для значения второго уравнения; с) если остаток равен 11 для значения третьего уравнения. То в исходном ряду чисел от 1 до n число помечается как простое. Замечание: если какое-то число Z присутствует в значениях нескольких уравнений (допустим a и b), и остаток от деления на 12 этого числа удовлетворяет условиям обоих групп, то число помечается два раза: сначала как простое, а потом как составное. 5. На последнем этапе проверяется кратность помеченных чисел квадратам простых чисел из диапазона от 5 до sqrt(n). Если число кратно квадрату, то оно помечается как составное. Пример работы алгоритма для n = 40. 1. Выписываем все натуральные числа из диапазона от 1 до 40. 2. Вычисляем значения уравнений для каждой пары чисел x и y.
5 — простое число, 6 — составное, значит проверяем на кратность 5^2=25 помеченные числа. В результате 25 — нужно вычеркнуть. В итоге остаются только простые числа от 1 до 40.
Алгоритм имеет асимптотическую сложность и требует бит памяти. На входных значениях порядка решето Аткина быстрее решета Эрастофена в 9.2 раза. Приведу график роста превосходства алгоритма Аткина на числах от 2 до : В результате можно наблюдать следующую скорость выполнения:
Алгоритм простого деления Описание алгоритма: (http://algolist.manual.ru/maths/teornum/factor/trial.php)
Это самый простой, наивный метод - метод простого деления. Практически при любом алгоритме факторизации оптимально использовать этот способ до некоторой границы B, чтобы убрать малые делители. Наиболее наивный подход - просто делить на все числа подряд до корня из N. Пусть мы хотим поделить N на все простые числа до корня из N. Для этого мы можем иметь или не иметь в своем распоряжении достаточно большую таблицу простых чисел. Если это не так, то, очевидно, мы можем делить N на числа d в заданных классах эквивалентности, например, 1 и 5 по модулю 6, или 1,7,11,13,17,19,23,29 по модулю 30. Тогда мы проделаем много бессмысленных делений (на составные числа), однако результат останется верным. Таким образом, можно составить следующий алгоритм:
Предположим, что у нас уже есть таблица простых чисел: p[1] = 2, p[2] = 3, ... , p[k], где k > 3, массив t := [6,4,2,4,2,4,6,2], и индекс j, такой что если p[k] mod 30 равно 1,7,11,13,17,19,23 или 29, то j := 0,1,2,3,4,5,6 или 7 соответственно.
Получив на входе положительное целое число N, этот алгоритм пытается разложить его на множители, и, если это не получается, то N - число без простых делителей, меньших либо равных B.
1. [Инициализация] 2. [Cледующее простое] 3. [Простое деление] 4. [Простое?] 5. [Следующий делитель] Заметим, что i = -1 пока мы используем нашу таблицу простых и i >= 0 если нет. Метод весьма полезен для удаления малых множителей, однако его не следует использовать для полной факторизации, кроме тех случаев, когда N - очень маленькое ( например, N < 108).
©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|