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

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

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

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

A=X*Y,

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

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

image-loader.svg

Получаем, что бы последняя цифра числа А была равна 1 — последние цифры чисел Х и Y должны быть 1 и 1 (1×1=1) или 3 и 7 (3×7=21) или 9 и 9 (9×9=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. Тогда. Произведем умножение в столбик.

image-loader.svg

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

image-loader.svg

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

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

image-loader.svg

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

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

image-loader.svg

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

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

© Habrahabr.ru