Вероятностные алгоритмы теста простоты

итак давайте сначала поясним что кроется за новым для нас с принципом работы вероятно снова алгоритма алгоритм принимает некое число n и если оно простое наш алгоритм со стопроцентной уверенностью ответят что оно простое и никогда не назовет его составным а если оно составное то нашим алгоритмом будет позволено очень маленькая вероятность на ошибку е когда он назовет число простым и наоборот с вероятностью единица минус вероятность ошибки е число будет верно определена как составное начнем с простого примера пусть есть универсальное конечное множество целых чисел мы берем число из этого множества и обозначаем его н дальше вводим н в наш автомат ранее мы с вами по сути перебирали все числа от единицы до корня квадратного из n и проверяли не делится ли n на какой-нибудь из них хотя для экономии времени мы искали только простые делители и если n делится на текущее число значит and составное потому что мы нашли делитель если нет то пока с точностью ничего сказать нельзя увеличиваем а и снова проверяем на делимость и когда мы переберем все потенциальные делитель и только тогда мы можем сказать да число n простое поскольку делителей у него не нашлось а что если мы выберем несколько случайных целых чисел и проведем лишь несколько проверок на делимость проведем так сказать экзамен на случайно выбранных билетах если некое число n является составным значит у него где-то есть хотя бы один делитель как минимум один у большинства составных чисел делителей много и мы берем некое случайное число а от единицы до корня квадратного из n и проверяем делится ли n на а значит мы на сто процентов уверены что n составное если не делятся то мы почти ничего не узнали за исключением того что оно может быть простым и чтобы убедиться в этом мы генерируем еще несколько случайных чисел a и каждый раз снова проверяем на делимость и возможно после 100 или 1000 таких операций можно прекратить процесс и сказать число n скорее всего простое с некой степени уверенности скажем 99,99 процентов и здесь принцип похож на задачу об условной вероятности из прошлого видеоролика в ней мы пытались угадать какая монетка была подброшена обычное или двусторонняя здесь выпадение решки это нахождение делителя признак обычной монетки а если выпал орел мы просим перебросить монетку еще раз в этой задачи уже после 5 орлов подряд мы с уверенностью свыше 90 процентов можем остановить игру и сказать думаю монетка двусторонняя я написал программу которая сравнивает наш старый метод проверки числа на простоту с новым алгоритмом проверки случайных делителей причем я взял самый быстрый алгоритм которые предложили мне в комментариях и указал в начале программы его автора и ссылку и так переменная обозначает количество случайных попыток начнем с маленького значения например с трех попыток как вы видите на небольших вводных числах если n простое то и алгоритм всегда определит его простым но если водное число составное вероятностные алгоритму начинает ошибаться и может не правильно определить его как простое проблему можно исправить увеличив количество попыток и таким образом снизив вероятность ошибки и уже видно что результат более-менее похож на правду но с увеличением водного числа растет и вероятность погрешности и мне приходится соответственно увеличивать количество попыток тогда результаты снова становится почти безошибочным оба алгоритма выдают один и тот же ответ но для очень больших чисел для приемлемой достоверности необходимо будет производить 1000 проверок и получается что наш алгоритм не сильно сократил количество проверок да и первоначальный способ перебора делителей по-прежнему работает лучше дело в том что вероятность ошибки при проверке на делимость слишком велика но мы все равно движемся в верном направлении нужно лишь придумать другую проверку например придумать некую формулу для быстрого отбора простых чисел пусть в нее входят не только сама проверяемое число n но и некое случайное число а дальше мы проверяем число на простоту при помощи этой формулы спасибо что подписывайтесь на наш канал мы будем рады услышать ваше мнение по поводу этого видео если у вас возникли вопросы касательно данного видеоролика то напишите их в комментариях и мы с удовольствием постараемся ответить на них