Задание 6 (индивидуальное): алгоритмы проверки на простоту

Указания

Для выполнения задания необходимо использовать операции с длинными целыми числами, реализованными в задании 1. Для каждого из заданий необходимо найти график времени работы алгоритма в зависимости от длины входных данных.

Варианты

  1. Решето Эратосфена, числа необходимо хранить в контейнере "множество" (std::set <>).
  2. Перебор делителей вида 6 k ± 1.
  3. Тест Ферма.
  4. Тест Миллера – Рабина.
  5. Тест Соловея – Штрассена.
  6. Тест Люка.
  7. Тест Прота.
  8. Тест Поклингтона.
  9. Тест Агравала – Каяла – Саксены.
  10. Решето Аткина.
  11. Тест Голдвассера – Килиана.
  12. Тест Аткина – Морейна.