Проверка числа на простоту
Простых чисел бесконечное множество. В интернете в свободном доступе можно найти таблицы простых чисел до 21 000 000. Существующие методы проверки чисел на простоту очень сложны, не универсальны, поэтому мной разработан еще один способ проверки числа на простоту для чисел больше 10.
Простое число – целое положительное число, которое имеет два различных натуральных делителя: единицу и самого себя, то есть, если число можно разложить на множители значит оно не простое – а составное.
Пусть А – натуральное число, тогда
где Х и 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х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. Тогда . Произведем умножение в столбик.
Получаем, 100*x*y+10*(x+y)+1=A , откуда
Мы получили уравнение с двумя переменными при известном А. Решений данного уравнения множество, но при условии, что х и у – натуральные, количество решений конечно, или вообще их нет в целочисленном выражении. Получается, если решений нет в натуральных числах, то А является простым числом.
Для остальных пар выполняем аналогичные действия и получаем:
Решение полученных уравнений при больших А – задача трудоемкая, поэтому была написана программа для определения простоты числа согласно нашим уравнениям.
Код написан на Visual Basic.
Данный макрос, написанный на Visual Basic, имеет ряд недостатков. Он ограничен вычислительными возможностями excel и при больших числах более 400млн для предположительно простых чисел выдает ошибку о переполнении. Но, для составных чисел, так как алгоритм после нахождения одного из возможных множителей дальше не считает, макрос считает большие числа. Время расчета в VB составляет 1-5 секунд. Так как расчетные уравнения рассчитаны для чисел больших 10, то простота чисел из первого десятка просто добавлена в макрос.
Таким образом, получен математический способ проверки числа на простоту и написан программный код в Visual Basic для его реализации. Но так как вычислительные возможности в Visual Basic ограничены, для проверки простоты больших чисел требуется написание программы на других языках программирования.
- простые числа
- тест проверки числа на простоту
- математика
- программирование
- visual basic
- Программирование
- Математика
- Visual Basic for Applications
Для заданного числа N проверить, является ли оно простым. на языке C?
int isPrime(int n) <
if (n for (int i = 2; i * i if (n % i == 0) return 0; // n делится на i без остатка, значит, n составное число
>
return 1; // n не делится на никакое число кроме 1 и самого себя, значит, n простое число
>
int main() <
int n;
scanf(«%d», &n);
printf(«%d», isPrime(n));
return 0;
>
Функция isPrime принимает целочисленный аргумент n и возвращает 1, если n является простым числом, и 0 в противном случае.
Сначала проверяем, является ли n равным 1 или меньшим. Если это так, то n не является простым числом, поэтому возвращаем 0.
Затем мы проверяем, делится ли n на какое-либо число от 2 до корня из n. Если да, то n является составным числом и мы возвращаем 0.
Если никакое число от 2 до корня из n не делит n без остатка, то n является простым числом, поэтому возвращаем 1.
В функции main считываем входное значение n, вызываем функцию isPrime и выводим ее результат.
При этом, return 0 не меняем, так как это требование задачи.
Да не меняй return 0; , он вообще в в этой программе не нужен, соответствующий ему код в программе на C компилятором автоматически сгенерируется и без него 🙂
Как проверить является ли число простым в С++
Даже на языке программирования C++ можно проверить является ли число простым несколькими способами.
Вариант первый:
#include
using namespace std;
bool checkPrimeNumber(int);
int main()
int n;
cout
cin >> n;
if (checkPrimeNumber(n))
cout
else
cout
return 0;
>
bool checkPrimeNumber(int n)
bool isPrimeNumber = true;
// 0 и 1 не являются простыми числами
if (n == 0 || n == 1)
isPrimeNumber = false;
>
else
for (int i = 2; i <= n / 2; ++i)
if (n % i == 0)
isPrimeNumber = false;
break;
>
>
>
return isPrimeNumber;
>
Ели запустить в работу эту программу, тогда в результате будет следующее:
Введите целочисленное положительное значение: 23
23 — это простое число
В С++ можно определить простое число или нет другим способом. Например, таким:
#include
using namespace std;
int main()
int i, n;
bool isPrimeNumber = true;
cout
cin >> n;
// 0 и 1 не являются простыми числами по умолчанию
if (n == 0 || n == 1)
isPrimeNumber = false;
>
else
for (i = 2; i <= n / 2; ++i)
if (n % i == 0)
isPrimeNumber = false;
break;
>
>
>
if (isPrimeNumber)
cout
else
cout
return 0;
>
Если запустить эту программу в работу, тогда ее результатом будет, как и в предыдущем случае, например, такое:
Введите целочисленное положительное значение: 29
29 — это простое число
Заключение
Проверка: простое ли число на С++ делается несложно. Чтобы определить просто е число или нет, вы можете воспользоваться одной из описанных выше версий программы проверки на С++, либо придумать собственную.
Мы будем очень благодарны
если под понравившемся материалом Вы нажмёте одну из кнопок социальных сетей и поделитесь с друзьями.
Сумасшедший способ проверить, является ли число простым, используя регулярное выражение
В поисках алгоритмов для выявления простых чисел, вы где-нибудь, да встречали подобное выражение:
Что это? Это способ проверки, является ли число простым. Вам даже не придётся писать цикл for!
Я тоже так думал. Поэтому решил, что будет интересно разобрать и разъяснить это выражение шаг за шагом на случай, если кому-то любопытно.
Примечание: Я знаю, регулярные выражения иногда похожи на абракадабру (особенно, всё что между символами / ), но я обещаю, что всё обретёт смысл. Оставайтесь со мной.
Так что же здесь происходит?
В целом, суть функции сводится к трём шагам:
1. Привести число к его унарной форме
2. Проверить, является ли оно 0 или 1
3. Проверить, является ли оно кратным любому числу больше 1
Шаг №1
Во-первых, нам нужно привести проверяемое число в унарную форму. Унарную систему можно представить как счёт на палочках (т.е. 3 записывается как «111», а 4 как «1111» и т.д.).
За это отвечает данный кусок кода:
Этот код создаёт массив с n + 1 пустыми слотами, далее присоединяет к этим пустым значениям — единицы.
Я предпочитаю использовать метод String.prototype.repeat() из ES6, который выглядит вот так:
Такой способ избавляет от необходимости сначала создавать массив, а потом присоединять все его элементы в строку. И ещё, так лучше читается. Но старый способ очень распространён в интернете, поэтому я решил показать оба.
Отлично! Двигаемся дальше!
Шаг №2
Теперь мы начинаем проверять, соответствует ли унарная версия нашего числа регулярному выражению. Это выражение можно разбить на две части, которые разделены символом | (который работает как оператор OR).
Левая часть выглядит так:
Давайте пройдёмся по каждому символу:
Он указывает регулярному выражению, что необходимо начинать проверку с начала строки. Таким образом, поиск паттернов начнётся с начала, а не с середины, конца или где бы то ни было ещё. Это противоположность символа $ , который указывает нашему выражению, где должен быть конец строки. Другими словами, вся строка целиком должна соответствовать выражению и не должно быть остатка.
Здесь единица указывает, что в строке необходимо искать символ «1». Мы могли бы создать нашу «унарную строку» из двоек (т.е. 3 станет «222» и т.д.), тогда вместо 1 мы бы написали 2. Другими словами, этот символ должен совпадать с тем, что вы указывали, создавая строку.
Он указывает на то, что предыдущий символ необязателен, таким образом выражение сверит отсутствие “1” или одну «1» (“ ” или “1”).
Как я уже говорил — это противоположность символа ^ . Так мы узнаём, что в конце нет остатка.
Итак, эта часть регулярного выражения завершает шаг №2 — проверку, было ли число 0 или 1.
Шаг №3
Здесь начинается самое интересное. Нам нужно проверить, кратно ли число чему-то большему, чем единица. Если да, то оно не является простым числом. Давайте рассмотрим правую часть выражения:
Здесь у нас такой же паттерн ^. $ , указывающий места начала и конца проверки строки. Сперва давайте посмотрим, что происходит в скобках.
Скобки здесь нужны для группировки, это важно, потому что мы проверяем кратность. Если мы хотим убедиться, что наше число не кратно двум, нам нужно сгруппировать все единицы в виде «11…» и узнать есть ли остаток.
Первые две единицы внутри скобок, являются тем же что и 1 из предыдущей части. Они приводят наше число в соответствие с унарной версией строки.
Символ + указывает на необходимость соответствия одному или нескольким символам, предшествующим ему. Таким образом, необходимо как минимум две “1” для сопоставления. При этом любое количество “1”, большее чем это, тоже подойдёт.
Символ ? — очень важен. Он делает + менее «жадным». Т.е. сначала, выражение будет проверять наименьшую из возможных частей строки. Проверка начнётся с двух “1”, далее три “1”, потом четыре и т.д. Без символа ? выражение будет проверять строку столько, сколько это возможно, в нашем случае это вся строка, так как наша строка содержит только один символ.
Теперь у нас есть группа из двух или более “1”. Нам нужно проверить кратность и остаток во всей строке. За это отвечает \1+? .
Первая часть \1 называется обратная ссылка. Она ссылается на то, что было в первой группе нашего выражения между скобок. Представьте, что это своеобразная переменная в выражении.
Следом идёт +? , этот символ, должен быть вам знаком. Это «не жадная» проверка.
И так, если (11+?) совпадает со строкой “11”, значит наша обратная ссылка тоже будет соответствовать “11”. Наше регулярное выражение ищет всё что кратно “11”, начиная с “1111”, далее “111111” и т.д. Если наше число нечётное, поиск завершится неудачей, тогда добавляется ещё одна “1” внутрь скобок и проверка на кратность, теперь уже “111”, повторяется.
Если выражение возвратит true после проверки, значит наше число: а) 0 или 1, или б) кратно числу большему чем 1. То есть оно не является простым ( ! )! Здорово, правда?
Посмотрите ещё раз этот код, чтобы проверить всё ли вы поняли:
Ещё есть версия с красивым синтаксисом ES6, которая позволяет избежать создания необязательного массива:
Пока это всё что я хотел показать. Спасибо за внимание. Надеюсь, вам было интересно, и вы готовы создавать собственные регулярные выражения.
Несколько человек спрашивали меня об эффективности проверки простых чисел таким способом. Мне стоило упомянуть с самого начала (прошу прощение что не сделал этого), что это не самый эффективный способ проверки, является ли число простым.
Типичные методы выявления простых чисел, проверяют только делители до квадратного корня числа, но здесь мы проверяем всё до половины числа.
Регулярное выражение само по себе только часть проблемы. String.prototype.repeat() — это итерация которая повторяется n-количество раз, а для очень длинных чисел это требует много времени.
Регулярное выражение также ограничено тем, что максимальная длина строки в большинстве браузеров около 268 миллионов, т.е. вы не сможете проверить более длинные простые числа (например, моё любимое 1000000000000066600000000000001).
В общем, данный способ не стоит применять на практике. Я лишь хотел разобрать этот способ в качестве упражнения.