Comments 26
Не «до 21000000», а 21 миллион простых чисел, наверное?
Ибо с определением простоты до 21M никаких проблем, вообще, не предвидится.
Ну и код скриншотом - почему?
Возможно потому что если будет можно просто скопипастить и запустить окажется что эта супер-штука или вообще не работает, или работает совсем не так быстро как написано, а в таком варианте заморачиваться с OCR или перепечатывать всем влом, поэтому писать можно почти что угодно - проверять же никто не будет.
Код
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 не знаком вообще и судя по синтаксису — к счастью.
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 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
2. Есть специальная секция блок кода. для markdown выглядит как-то так
```vbscript
dim some code
````
для легаси html
<source lang="vbscript">
dim some code
</source>
3. Чтобы людям не приходилось скроллить здоровенные пеленки есть блок спойлера под который обычно принято прятать длинные блоки кода или нежелательные картинки.
содержимое примера
4. Бонусные очки идут за нормальное оформление формул в статье.
Чем-то напоминает научную статью, написанную студентом. Вполне можно попробовать отправить на какую-нибудь конференцию. Конечно, оформив соответствующим образом.
Решение полученных уравнений при больших А – задача трудоемкая,
Более того - заключается в переборе всех потенциально возможных вариантов. Собственно, как и исходная задача. Ускорение возможно только в том случае, если вы сможете показать что суммарное количество вариантов в вашем способе будет меньше чем хотя бы в лобовом переборе нечетных чисел от 3 до SQRT(N).
Да, честно говоря, получается. Так как всё множество простых чисел тут разбивается на четыре части (равные или нет? На бесконечности, по логике, равные), где используются разные формулы для проверки простоты числа, то, по банальной логике, это вчетверо быстрее, чем проверка на остаток деления в лоб.
Чувствуется какой-то неочевидный подвох, но он неочевиден.
С другой стороны, что мешает нам расширить систему счисления выше десятки и получить больше ветвлений?
Так как всё множество простых чисел тут разбивается на четыре части
На самом деле не факт что разбивается на части. Если бы оно разбивалось, значит можно было точно доказать что множества допустимых корней у разных уравнений не пересекаются, а значит перебирать действительно нужно в 4 раза меньше. Но я сходу не вижу почему это может быть так.
Я тоже считаю, что данный алгоритм считает быстрее как минимум в четыре раза, а может и больше, так как алгоритм не считает все возможные варианты при определении первого делителя.
Подвохов нет, так как вся суть в разделении на четыре группы, а остальное дело техники.
Расширять систему выше десятки не рационально, так как теряется вся суть метода, тем более, что он работает на каждом десятке числового ряда.
Я тоже считаю, что данный алгоритм считает быстрее как минимум в четыре раза
"Какие будут ваши доказательства?"
Берем простое число 10110091, чтоб проверить, его на простоту по вашему алгоритму надо сделать минимум 91911 итераций, ибо только при x большем чем 91910 вы получите y меньше 1 и дальше проверять смысла не будет. При этом проверяя самым обычным перебором всех нечетных чисел до sqrt(10110091) надо сделать всего 1589 итераций, что в 57 раз меньше.
Более того — заключается в переборе всех потенциально возможных вариантов. Собственно, как и исходная задача
Не совсем: проверка числа на простоту, в отличие от факторизации, решается за полиномиальное время
... или 9 и 9 (9х10=81).
Но как?! Походу у Вас ошибка в расчетах..
Существующие методы проверки чисел на простоту очень сложны, не универсальны
А у вас прям ванлайнер получился, можно подумать. Тест Миллера-Рабина тоже довольно простой
В интернете в свободном доступе можно найти таблицы простых чисел до 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 раз больше), причём каждая итерация ещё и вычислительно тяжелее.
Проверялась ли корректность работы алгоритма? Таблица первых нескольких млн простых чисел известна, можно сгенерировать свою и сравнить, например.
Проверялось ли быстродействие алгоритма по сравнению с другими аналогичными?
Уже одно то, что автор пытается спекулировать на десятичной системе счисления - говорит о серьезных проблемах в таком подходе. Числа они ведь не в курсе, что у нас десять пальцев. Они просто есть - без относительно того, как мы их записываем. Просто обратим внимание на то, какие числа он использует в этих спекуляциях:
1,2,3,5,7
Хм... как интересно. Да ведь они простые!
Возьмем систему счисления из 12 знаков (добавим a,b), и ву-а-ля - туда уже можно добавить b (11), и начать спекулировать еще и на нем. В общем... суть, я думаю, понятна. Эти эвристики строятся на системе записи. Но вот есть проблемка - человек, в принципе, не может считать быстрее компьютера. А компьютер считает нулями и единицами. В итоге, вы потеряете гораздо больше вычислительного времени на переводах чисел из двоичной системы в десятичную, чем получите выгоды от этих эвристик. Если бы у нас был компьютер с изначально десятичной системой, то эти эвристики имели бы место быть, и (уж поверьте) ими бы уже воспользовались.
Уже одно то, что автор пытается спекулировать на десятичной системе счисления - говорит о серьезных проблемах в таком подходе.
Это не проблема. Когда мы рассматриваем последнюю цифру, то это просто вычисления по модулю 10. Ничего плохого в таком подходе самом по себе нет. Переход к вычислениям по модулю — это довольно частый приём при решении теоретико-числовых задач.
Например, одна из оптимизаций при проверке числа на простоту — это перебор делителей, у которых 1 или 5 в 6-ричной системе, и это даёт ускорение на 30 %, так как мы не рассматриваем цифру 3.
Мы знаем, что простые числа не четные
Нет:
Последовательность простых чисел начинается так:
2, 3, 5, 7
2 это единственное четное простое.
Проверка числа на простоту