Простых чисел бесконечное множество. В интернете в свободном доступе можно найти таблицы простых чисел до 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х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 ограничены, для проверки простоты больших чисел требуется написание программы на других языках программирования.
Комментарии (26)
fougasse
11.10.2021 19:49+2Не «до 21000000», а 21 миллион простых чисел, наверное?
Ибо с определением простоты до 21M никаких проблем, вообще, не предвидится.
Ну и код скриншотом - почему?
GerrAlt
11.10.2021 21:13+1Возможно потому что если будет можно просто скопипастить и запустить окажется что эта супер-штука или вообще не работает, или работает совсем не так быстро как написано, а в таком варианте заморачиваться с OCR или перепечатывать всем влом, поэтому писать можно почти что угодно - проверять же никто не будет.
GeMir
11.10.2021 21:31+4Код
Sub число() Dim x As Long, y As Double, A As Long, a1 As Double, b As Long, c As Long, d As Double, d1 As Long, d2 As Double, d3 As Long, d4 As Double, d5 As Long, y1 As Long, y2 As Double, y3 As Long, y4 As Double, y5 As Long, W As Integer x = 1 A = InputBox("Введите число") a1 = A / 10 b = Fix(a1) c = A - 10 * b d = A / 3 d1 = Fix(d) d2 = A / 7 d3 = Fix(d2) d4 = A / 9 d5 = Fix(d4) y = 10 y2 = 10 y4 = 10 W = 1 If c = 1 And d1 <> d And d2 <> d3 And d4 <> d5 Then Do While y >= 0 Or y2 >= 0 Or y4 >= 0 And W = 1 y = (A - 21 - 70*x) / (100*x + 30) y1 = Fix(y) y2 = (A - 81 - 90*x) / (100*x + 90) y3 = Fix(y2) y4 = (A - 1 - 10*x) / (100*x + 10) y5 = Fix(y4) If y = y1 Or y2 = y3 Then W = 0 If y5 = y4 Then If y4 <> 0 Then W = 0 x = x + 1 Loop Else: End If If c = 3 And d1 <> d And d2 <> d3 And d4 <> d5 Then Do While y >= 0 Or y2 >= 0 And W = 1 y = (A - 3 - 30*x) / (100*x + 10) y1 = Fix(y) y2 = (A - 63 - 90*x) / (100*x + 70) y3 = Fix(y2) If y = y1 Or y2 = y3 Then W = 0 x = x + 1 Loop Else: End If If c = 7 And d1 <> d And d2 <> d3 And d4 <> d5 Then Do While y >= 0 Or y2 >= 0 And W = 1 y = (A - 7 - 70*x) / (100*x + 10) y1 = Fix(y) y2 = (A - 27 - 90*x) / (100*x + 30) y3 = Fix(y2) If y = y1 Or y2 = y3 Then W = 0 x = x + 1 Loop Else: End If If c = 9 And d1 <> d And d2 <> d3 And d4 <> d5 Then Do While y >= 0 Or y2 >= 0 y4 >= 0 And W = 1 y = (A - 9 - 90*x) / (100*x + 10) y1 = Fix(y) y2 = (A - 9 - 30*x) / (100*x + 30) y3 = Fix(y2) y4 = (A - 49 - 70*x) / (100*x + 70) y5 = Fix(y4) If y = y1 Or y2 = y3 Or y4 = y5 Then W = 0 x = x + 1 Loop Else: End If If c = 2 Or c = 4 Or c = 6 Or c = 8 Or c = 0 Or c = 5 Or d = d1 Or d2 = d3 Or d4 = d5 Then W = 0 If A = 3 Or A = 5 Or A = 2 Or A = 7 Then W = 1 If A = 1 Then W = 0 If W = 1 Then MsgBox "число простое" Else: MsgBox "число составное" End SubИзвиняюсь за возможные опечатки. С Visual Basic не знаком вообще и судя по синтаксису — к счастью.
kurduk Автор
12.10.2021 11:57+2Sub число()
Dim x As Long, y As Double, A As Long, a1 As Double, b As Long, c As Long, d As Double, d1 As Long, d2 As Double, d3 As Long, d4 As Double, d5 As Long, y1 As Long, y2 As Double, y3 As Long, y4 As Double, y5 As Long, W As Integer
x = 1
A = InputBox("Введите число")
a1 = A / 10
b = Fix(a1)
c = A - 10 * b
d = A / 3
d1 = Fix(d)
d2 = A / 7
d3 = Fix(d2)
d4 = A / 9
d5 = Fix(d4)
y = 10
y2 = 10
y4 = 10
W = 1
If c = 1 And d1 <> d And d2 <> d3 And d4 <> d5 Then
Do While y >= 0 Or y2 >= 0 Or y4 >= 0 And W = 1
y = (A - 21 - 70 * x) / (100 * x + 30)
y1 = Fix(y)
y2 = (A - 81 - 90 * x) / (100 * x + 90)
y3 = Fix(y2)
y4 = (A - 1 - 10 * x) / (100 * x + 10)
y5 = Fix(y4)
If y = y1 Or y2 = y3 Then W = 0
If y5 = y4 Then If y4 <> 0 Then W = 0
x = x + 1
Loop
Else:
End If
If c = 3 And d1 <> d And d2 <> d3 And d4 <> d5 Then
Do While y >= 0 Or y2 >= 0 And W = 1
y = (A - 3 - 30 * x) / (100 * x + 10)
y1 = Fix(y)
y2 = (A - 63 - 90 * x) / (100 * x + 70)
y3 = Fix(y2)
If y = y1 Or y2 = y3 Then W = 0
x = x + 1
Loop
Else:
End If
If c = 7 And d1 <> d And d2 <> d3 And d4 <> d5 Then
Do While y >= 0 Or y2 >= 0 And W = 1
y = (A - 7 - 70 * x) / (100 * x + 10)
y1 = Fix(y)
y2 = (A - 27 - 90 * x) / (100 * x + 30)
y3 = Fix(y2)
If y = y1 Or y2 = y3 Then W = 0
x = x + 1
Loop
Else:
End If
If c = 9 And d1 <> d And d2 <> d3 And d4 <> d5 Then
Do While y >= 0 Or y2 >= 0 Or y4 >= 0 And W = 1
y = (A - 9 - 90 * x) / (100 * x + 10)
y1 = Fix(y)
y2 = (A - 9 - 30 * x) / (100 * x + 30)
y3 = Fix(y2)
y4 = (A - 49 - 70 * x) / (100 * x + 70)
y5 = Fix(y4)
If y = y1 Or y2 = y3 Or y4 = y5 Then W = 0
x = x + 1
Loop
Else:
End If
If c = 2 Or c = 4 Or c = 6 Or c = 8 Or c = 0 Or c = 5 Or d = d1 Or d2 = d3 Or d4 = d5 Then W = 0
If A = 3 Or A = 5 Or А=2 or A = 7 Then W = 1
If A = 1 Then W = 0
If W = 1 Then MsgBox "число простое" Else: MsgBox "число составное"
End Sub
domix32
12.10.2021 13:17+31. Это должно быть в посте
2. Есть специальная секция блок кода. для markdown выглядит как-то так```vbscript dim some code ````
для легаси html<source lang="vbscript"> dim some code </source>
3. Чтобы людям не приходилось скроллить здоровенные пеленки есть блок спойлера под который обычно принято прятать длинные блоки кода или нежелательные картинки.Примерсодержимое примера
4. Бонусные очки идут за нормальное оформление формул в статье.
yaguarundi
11.10.2021 19:57Чем-то напоминает научную статью, написанную студентом. Вполне можно попробовать отправить на какую-нибудь конференцию. Конечно, оформив соответствующим образом.
lorc
11.10.2021 19:57+3Решение полученных уравнений при больших А – задача трудоемкая,
Более того - заключается в переборе всех потенциально возможных вариантов. Собственно, как и исходная задача. Ускорение возможно только в том случае, если вы сможете показать что суммарное количество вариантов в вашем способе будет меньше чем хотя бы в лобовом переборе нечетных чисел от 3 до SQRT(N).
ZodDZverev
11.10.2021 20:58Да, честно говоря, получается. Так как всё множество простых чисел тут разбивается на четыре части (равные или нет? На бесконечности, по логике, равные), где используются разные формулы для проверки простоты числа, то, по банальной логике, это вчетверо быстрее, чем проверка на остаток деления в лоб.
Чувствуется какой-то неочевидный подвох, но он неочевиден.
С другой стороны, что мешает нам расширить систему счисления выше десятки и получить больше ветвлений?
lorc
11.10.2021 21:42Так как всё множество простых чисел тут разбивается на четыре части
На самом деле не факт что разбивается на части. Если бы оно разбивалось, значит можно было точно доказать что множества допустимых корней у разных уравнений не пересекаются, а значит перебирать действительно нужно в 4 раза меньше. Но я сходу не вижу почему это может быть так.
kurduk Автор
11.10.2021 21:56Я тоже считаю, что данный алгоритм считает быстрее как минимум в четыре раза, а может и больше, так как алгоритм не считает все возможные варианты при определении первого делителя.
Подвохов нет, так как вся суть в разделении на четыре группы, а остальное дело техники.
Расширять систему выше десятки не рационально, так как теряется вся суть метода, тем более, что он работает на каждом десятке числового ряда.
Politura
12.10.2021 09:23+1Я тоже считаю, что данный алгоритм считает быстрее как минимум в четыре раза
"Какие будут ваши доказательства?"
Берем простое число 10110091, чтоб проверить, его на простоту по вашему алгоритму надо сделать минимум 91911 итераций, ибо только при x большем чем 91910 вы получите y меньше 1 и дальше проверять смысла не будет. При этом проверяя самым обычным перебором всех нечетных чисел до sqrt(10110091) надо сделать всего 1589 итераций, что в 57 раз меньше.
kurduk Автор
12.10.2021 12:36+1Алгоритм быстрее, чем просто перебор всех возможных делителей. Но ведь никто не запрещает взять мой алгоритм и способ с sqrt и объединить их. Будет еще быстрее.
lightln2
11.10.2021 21:58+1Более того — заключается в переборе всех потенциально возможных вариантов. Собственно, как и исходная задача
Не совсем: проверка числа на простоту, в отличие от факторизации, решается за полиномиальное время
Scratch
11.10.2021 21:45+4Существующие методы проверки чисел на простоту очень сложны, не универсальны
А у вас прям ванлайнер получился, можно подумать. Тест Миллера-Рабина тоже довольно простой
masai
11.10.2021 22:32+7В интернете в свободном доступе можно найти таблицы простых чисел до 21 000 000.
http://www.primos.mat.br/indexen.html — вот, например, миллиард первых простых чисел. Можно и больше найти, если нужно.
Кстати, вы можете вставить код как код, а не в виде картинки. К сожалению, сейчас прочитать код очень тяжело, не говоря уж о том, чтоб проверить его.
Кстати, как я понимаю, этот метод будет медленнее, чем простой метод из Википедии:
def is_prime(n: int) -> bool: """Primality test using 6k+-1 optimization.""" if n <= 3: return n > 1 if n % 2 == 0 or n % 3 == 0: return False i = 5 while i ** 2 <= n: if n % i == 0 or n % (i + 2) == 0: return False i += 6 return TrueДля числа порядка 1 миллиона потребуется около
итераций в худшем случае. Ваш код, как я понимаю, потребует примерно 10000 итераций в худшем случае (в 60 раз больше), причём каждая итерация ещё и вычислительно тяжелее.
unsignedchar
11.10.2021 23:15+1Проверялась ли корректность работы алгоритма? Таблица первых нескольких млн простых чисел известна, можно сгенерировать свою и сравнить, например.
Проверялось ли быстродействие алгоритма по сравнению с другими аналогичными?
greabock
11.10.2021 23:30+3Уже одно то, что автор пытается спекулировать на десятичной системе счисления - говорит о серьезных проблемах в таком подходе. Числа они ведь не в курсе, что у нас десять пальцев. Они просто есть - без относительно того, как мы их записываем. Просто обратим внимание на то, какие числа он использует в этих спекуляциях:
1,2,3,5,7
Хм... как интересно. Да ведь они простые!
Возьмем систему счисления из 12 знаков (добавим a,b), и ву-а-ля - туда уже можно добавить b (11), и начать спекулировать еще и на нем. В общем... суть, я думаю, понятна. Эти эвристики строятся на системе записи. Но вот есть проблемка - человек, в принципе, не может считать быстрее компьютера. А компьютер считает нулями и единицами. В итоге, вы потеряете гораздо больше вычислительного времени на переводах чисел из двоичной системы в десятичную, чем получите выгоды от этих эвристик. Если бы у нас был компьютер с изначально десятичной системой, то эти эвристики имели бы место быть, и (уж поверьте) ими бы уже воспользовались.masai
12.10.2021 00:34+2Уже одно то, что автор пытается спекулировать на десятичной системе счисления - говорит о серьезных проблемах в таком подходе.
Это не проблема. Когда мы рассматриваем последнюю цифру, то это просто вычисления по модулю 10. Ничего плохого в таком подходе самом по себе нет. Переход к вычислениям по модулю — это довольно частый приём при решении теоретико-числовых задач.
Например, одна из оптимизаций при проверке числа на простоту — это перебор делителей, у которых 1 или 5 в 6-ричной системе, и это даёт ускорение на 30 %, так как мы не рассматриваем цифру 3.
third112
12.10.2021 02:17+1Мы знаем, что простые числа не четные
Нет:
Последовательность простых чисел начинается так:
2, 3, 5, 72 это единственное четное простое.
VolodjaT
Это почему? Что мешает написать длинную арифметику на VB?
kurduk Автор
Возможно мои познания в программировании, а над "длинной арифметикой" я подумаю на досуге.
VolodjaT
https://ru.m.wikipedia.org/wiki/%D0%94%D0%BB%D0%B8%D0%BD%D0%BD%D0%B0%D1%8F_%D0%B0%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D0%BA%D0%B0
Вот алгоритмы
PS 99% что и для VB уже давно есть готовая библиотека