Проверка числа на простоту

Моя цель - предложение широкого ассортимента товаров и услуг на постоянно высоком качестве обслуживания по самым выгодным ценам.

Простых чисел бесконечное множество. В интернете в свободном доступе можно найти таблицы простых чисел до 21 000 000. Существующие методы проверки чисел на простоту очень сложны, не универсальны, поэтому мной разработан еще один способ проверки числа на простоту для чисел больше 10.

Простое число – целое положительное число, которое имеет два различных натуральных делителя: единицу и самого себя, то есть, если число можно разложить на множители значит оно не простое – а составное.

Пусть А – натуральное число, тогда

A=X*Y,

где Х и Y – натуральные числа.

Мы знаем, что простые числа не четные, и все числа, заканчивающиеся на 5 и 0 кратны пяти, значит, простые числа всегда заканчиваются на 1, 3, 7, 9. Выберем из таблицы умножения примеры, в которых последняя цифра произведения равна 1 или 3 или 7 или 9 (смотрим рисунок).

Получаем, что бы последняя цифра числа А была равна 1 – последние цифры чисел Х и Y должны быть 1 и 1 (1х1=1) или 3 и 7 (3х7=21) или 9 и 9 (9х10=81).

Что бы последняя цифра числа А была равна 3 – последние цифры чисел Х и Y должны быть равны 1 и 3 (1х3=3) или 7 и 9 (7х9=63).

Что бы последняя цифра числа А была равна 7 – последние цифры чисел Х и Y должны быть равны 1 и 7 (1х7=7) или 3 и 9 (3х9=27).

Что бы последняя цифра числа А была равна 9 – последние цифры числе Х и Y должны быть равны 1 и 9 (1х9=9) или 3 и 3 (3х3=9) или 7 и 7 (7х7=49).

Рассмотрим каждую пару последних цифр для Х и Y по отдельности.

Для пары 1 и 1. Пусть Х =х1, где 1 – последняя цифра числа Х, а х – оставшаяся цифровая часть числа Х без последнего числа. Аналогично Y=y1, где 1 -  последняя цифра числа Y, а y – оставшаяся цифровая часть числа Y. Тогда . Произведем умножение в столбик.

Получаем,    100*x*y+10*(x+y)+1=A         , откуда

Мы получили уравнение с двумя переменными при известном А. Решений данного уравнения множество, но при условии, что х и у – натуральные, количество решений конечно, или вообще их нет в целочисленном выражении. Получается, если решений нет в натуральных числах, то А является простым числом.

Для остальных пар выполняем аналогичные действия и получаем:

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

Код написан на Visual Basic.

Данный макрос, написанный на Visual Basic, имеет ряд недостатков. Он ограничен вычислительными возможностями excel и при больших числах более 400млн для предположительно простых чисел выдает ошибку о переполнении. Но, для составных чисел, так как алгоритм после нахождения одного из возможных множителей дальше не считает, макрос считает большие числа. Время расчета в VB составляет 1-5 секунд. Так как расчетные уравнения рассчитаны для чисел больших 10, то простота чисел из первого десятка просто добавлена в макрос.

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

Источник: https://habr.com/ru/post/582866/


Интересные статьи

Интересные статьи

На основе выступления на Numerous Numerosity: междисциплинарная встреча, посвященная понятиям мощности, ординальности и арифметики в различных науках. У всех должны быть числа… Не...
Популярный аргумент к ставшей вирусной публикации про коронавирус — да как же можно по трём случаям какую-то статистику выводить? Нельзя делать выводы по таким маленьким выборкам! Эту историю про...
Среди советов по улучшению юзабилити интернет-магазина, которые можно встретить в инете, один из явных лидеров — совет «сообщайте посетителю стоимость доставки как можно раньше».
В 1С Битрикс есть специальные сущности под названием “Информационные блоки, сокращенно (инфоблоки)“, я думаю каждый с ними знаком, но не каждый понимает, что это такое и для чего они нужны
Часть 0: Фракталы в простых числах. Часть 1: Фракталы в иррациональных числах. В статье присутствуют Gif и контрастные картинки. У эпилептиков может случиться эпилептический припадок. ...