3. Признак делимости на составное число
Простые и составные числа, определения, примеры, таблица простых чисел, решето Эратосфена.
Совет 1: Что такое простое число
Простые и составные числа
Как определить простое число
Перебор делителей Тест Ферма Тест Миллера-Рабина Китайская теорема об остатках. Простые числа — это числа, которые делятся только на себя и на 1; все остальные числа называются составными числами. Существует множество способов определения того, является ли число простым. Некоторые способы являются относительно простыми, но они не подходят для больших чисел. Другие способы, применимые для больших чисел, фактически представляют собой вероятностные алгоритмы, которые иногда ошибочно характеризуют число как простое или составное. Перебор делителей — самый легкий способ определить простоту числа. В случае малых чисел это, пожалуй, также и самый быстрый способ. Он основан на определении простого числа: В году французский математик Пьер Ферма впервые сформулировал теорему малая теорема Ферма , которая используется при определении простоты числа. Фактически, тест Ферма служит для определения составных чисел, а не простых. Тест Миллера-Рабина эффективно определяет, является ли число составным и лучше обрабатывает исключения, такие как числа Кармайкла. Сообщество Наугад Про нас Категории Свежие правки. Написать статью Категоризировать статьи Другие идеи Перебор делителей Тест Ферма Тест Миллера-Рабина Китайская теорема об остатках Простые числа — это числа, которые делятся только на себя и на 1; все остальные числа называются составными числами. Пусть n — проверяемое число. Согласно этому методу вы должны разделить число n на все возможные целые делители. Но существуют способы уменьшить количество делителей, которые нужно проверить. Определите, является ли число n четным. Любое четное число делится на 2. Если число n - четное, то можно сразу заявить, что оно не является простым то есть является составным числом. Для быстрого определения четности числа обратите внимание на его последнюю цифру. Если последняя цифра 2, 4, 6, 8,0, то число является четным и не является простым. Единственное исключение из этого правила - число 2. Так как оно делится нацело только на себя и на 1, то число 2 — простое число. Таким образом, число 2 является единственным четным простым числом. Разделите n на каждое число от 2 до n Так как делитель меньше делимого, то проверка всех делителей меньших n и больших 2 должна показать, является ли n простым числом. Вы начинаете с числа большего 2, потому что четные числа которые кратны 2 не являются простыми числами. Это далеко не самый эффективный способ тестирования чисел на простоту, но здесь существует несколько методов оптимизации проверки. Например, проверим число В этом случае разделим нацело 11 на 3, 4, 5, 6, 7, 8, 9, Так как ни одно из этих чисел не делит нацело 11, то число 11 — простое число. Чтобы сэкономить время, проверьте делители до округленного значения квадратного корня n. Проверка всех делителей от 2 до n-1 может занять много времени. Например, если вы хотите проверить число , то вам придется протестировать следующие делители: Но этого можно избежать — проверьте только делители от 2 до округленного значения квадратного корня n. Поэтому вы можете игнорировать делители числа n большие, чем квадратный корень n. Не нужно тестировать все делители от 3 до Вместо этого проверьте делители между 2 и округленным значением квадратного корня Округлите это число до 7. Для дальнейшей экономии времени тестируйте только простые делители. По определению любое составное число может быть выражено как произведение двух или более простых чисел. Поэтому деление числа n на составной делитель — лишняя операция, повторяющая многократное деление числа n на простые делители. Таким образом, вы можете еще больше сузить тестируемый ряд делителей. Это означает, что все четные делители и все делители, кратные простым числам, могут быть опущены. Квадратный корень из округляется до Простые делители от 2 до 11 это 3, 5, 7, Делители 4, 6, 8, 9, 10 можно опустить 9 кратно 3, а все остальные делители — четные числа. Таким образом, вы уменьшили ряд тестируемых делителей до четырех чисел. Делители 3, 5, 7, 11 не делят нацело число , поэтому оно - простое. Как отмечалось выше, иногда тест ложно идентифицирует составные числа как простые. Поэтому необходимо проверить ответ способ проверки ответа описан ниже. Например, проверим на простоту число Вычислите a n mod n. Вычисление этого выражения потребует некоторых знаний из модульной арифметики. В модульной арифметике при достижении определенного значения, называемого модулем, отсчет чисел начинается с нуля. Представьте это как часы: Модуль обозначается как mod n. Таким образом, вычислите a n mod n. Одним из способов вычисления будет вычислить a n , а затем разделить результат на n, а в качестве ответа записать остаток деления. В этом случае рекомендуется использовать специализированные калькуляторы с функцией модуля [2] , так как они мгновенно вычисляют остаток при делении больших чисел. Если у вас нет специализированного калькулятора, при вычислении остатка вручную используйте экспоненциальную запись числа. В нашем примере вручную вычислите 3 mod Напомним, что при возведении степени в степень показатели перемножаются: При получении остатка используйте его в дальнейших расчетах а не в качестве ответа. Продолжите вычисления с числом Если оно не соблюдено, то n — составное число. Если оно соблюдено, то n, скорее всего, простое число но не обязательно. Они называются числами Кармайкла самое малое из них - число Используйте числа Кармайкла в качестве гарантии правильности ответа. Пусть n - нечетное число, которое нужно протестировать на простоту. Если n — простое, то оно должно быть нечетным. Поэтому n-1 — четное. Так как n-1 — четное число, то оно может быть представлено в виде произведения числа 2 в некоторой степени на нечетное число. Вычислите a d mod n. Однако этот тест, как и тест Ферма, не может определить простоту числа с абсолютной уверенностью. Так как результат не равен 1 или -1, вы не можете утверждать, что n — простое число. Если результат не равен 1 или -1, вычислите a 2 d , a 4 d ,. Если один из результатов равен 1 или -1 mod n , то число n проходит тест Миллера- Рабина и, скорее всего, является простым. Если n проходит тест, проверьте ответ смотрите следующий шаг. Если n не проходит любой из этих тестов, то n — составное число. Продолжите проверку следующим образом: Здесь вы можете закончить вычисления. Выберите два числа — одно составное, а второе для проверки того, что оно простое. Выберите два неравных числа значения , которые больше нуля и меньше Числа1 и Числа2. Вычислите MMI математическую мультипликативную инверсию для Числа1 и Числа2. Создайте таблицу для каждой MMI вплоть до log2 модулей. Проверьте, что Число1 не является простым. Проверьте, что Число2 является простым. Повторите шаги с 1 по 7, по крайней мере, еще два раза. Если в шаге 7 вы получили 0: Используйте другое Число1, если Число1 не является простым. Используйте другое Число1, если Число1 является простым. В этом случае в шагах 6 и 7 вы должны получить 0. Используйте различные Значение1 и Значение2. Если в шаге 7 вы постоянно получаете 0, то с очень большой вероятностью Число2 является простым. Шаги с 1 по 7 могут привести к ошибке, если Число1 не является простым, а Число2 является делителем Числа1. Описанный метод работает во всех случаях, когда оба числа являются простыми. Причина, по которой необходимо повторять шаги с 1 по 7: Это редкий случай; выберите другое Число1 составное , если Число2 не является простым; тогда Число2 не будет равно нулю в шаге 7 за исключением случая, когда Число1 является делителем Числа2 - здесь простые числа всегда будут равны нулю в шаге 7. Советы Простые числа от до Даже в случае больших чисел начинают с тестирования малых делителей, а затем переходят к более сложным методам проверки простоты чисел если малые делители не найдены. Что вам понадобится Бумага, ручка, компьютер. Информация о статье Категории: Математика На других языках: Была ли эта статья полезной? Куки помогают сделать WikiHow лучше. Продолжая использовать наш сайт, вы соглашаетесь с нашими куки правилами. Главная страница Про wikiHow Terms of Use RSS Карта сайта Войти. Весь текст размещен под лицензией Creative Commons. Сделано с помощью Mediawiki.
События фильма последствия
Как выглядит мед полис нового образца
Фигурные стихи примеры на русском
Змеи восточного казахстана фото описание
Регулятор напряжения ваз 2110 схема