Возможно потому что если будет можно просто скопипастить и запустить окажется что эта супер-штука или вообще не работает, или работает совсем не так быстро как написано, а в таком варианте заморачиваться с OCR или перепечатывать всем влом, поэтому писать можно почти что угодно - проверять же никто не будет.

GeMir Oct 11 2021 at 21:31

Код

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 Oct 12 2021 at 11:57

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

unsignedchar Oct 12 2021 at 12:20

Может, тегом vbscript это обернуть? Или/и в спойлер спрятать?

domix32 Oct 12 2021 at 13:17

1. Это должно быть в посте
2. Есть специальная секция блок кода. для markdown выглядит как-то так

```vbscript
dim some code
````

для легаси html

<source lang="vbscript">
dim some code
&lt/source>

3. Чтобы людям не приходилось скроллить здоровенные пеленки есть блок спойлера под который обычно принято прятать длинные блоки кода или нежелательные картинки.

Пример

содержимое примера

4. Бонусные очки идут за нормальное оформление формул в статье.

yaguarundi Oct 11 2021 at 19:57

Чем-то напоминает научную статью, написанную студентом. Вполне можно попробовать отправить на какую-нибудь конференцию. Конечно, оформив соответствующим образом.

lorc Oct 11 2021 at 19:57

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

Более того - заключается в переборе всех потенциально возможных вариантов. Собственно, как и исходная задача. Ускорение возможно только в том случае, если вы сможете показать что суммарное количество вариантов в вашем способе будет меньше чем хотя бы в лобовом переборе нечетных чисел от 3 до SQRT(N).

ZodDZverev Oct 11 2021 at 20:58

Да, честно говоря, получается. Так как всё множество простых чисел тут разбивается на четыре части (равные или нет? На бесконечности, по логике, равные), где используются разные формулы для проверки простоты числа, то, по банальной логике, это вчетверо быстрее, чем проверка на остаток деления в лоб.

Чувствуется какой-то неочевидный подвох, но он неочевиден.

С другой стороны, что мешает нам расширить систему счисления выше десятки и получить больше ветвлений?

lorc Oct 11 2021 at 21:42

Так как всё множество простых чисел тут разбивается на четыре части

На самом деле не факт что разбивается на части. Если бы оно разбивалось, значит можно было точно доказать что множества допустимых корней у разных уравнений не пересекаются, а значит перебирать действительно нужно в 4 раза меньше. Но я сходу не вижу почему это может быть так.

kurduk Oct 11 2021 at 21:56

Я тоже считаю, что данный алгоритм считает быстрее как минимум в четыре раза, а может и больше, так как алгоритм не считает все возможные варианты при определении первого делителя.

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

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

Politura Oct 12 2021 at 09:23

Я тоже считаю, что данный алгоритм считает быстрее как минимум в четыре раза

"Какие будут ваши доказательства?"

Берем простое число 10110091, чтоб проверить, его на простоту по вашему алгоритму надо сделать минимум 91911 итераций, ибо только при x большем чем 91910 вы получите y меньше 1 и дальше проверять смысла не будет. При этом проверяя самым обычным перебором всех нечетных чисел до sqrt(10110091) надо сделать всего 1589 итераций, что в 57 раз меньше.

kurduk Oct 12 2021 at 12:36

Алгоритм быстрее, чем просто перебор всех возможных делителей. Но ведь никто не запрещает взять мой алгоритм и способ с sqrt и объединить их. Будет еще быстрее.

lightln2 Oct 11 2021 at 21:58

Более того — заключается в переборе всех потенциально возможных вариантов. Собственно, как и исходная задача

Не совсем: проверка числа на простоту, в отличие от факторизации, решается за полиномиальное время

casuss Oct 11 2021 at 21:02

... или 9 и 9 (9х10=81).

Но как?! Походу у Вас ошибка в расчетах..

kurduk Oct 11 2021 at 21:36

Спасибо, исправила.

kurduk Oct 11 2021 at 21:43

Это опечатка

Scratch Oct 11 2021 at 21:45

Существующие методы проверки чисел на простоту очень сложны, не универсальны

А у вас прям ванлайнер получился, можно подумать. Тест Миллера-Рабина тоже довольно простой

masai Oct 11 2021 at 22:32

В интернете в свободном доступе можно найти таблицы простых чисел до 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 миллиона потребуется около ${\sqrt{1000000} \over 6} \approx 167$ итераций в худшем случае. Ваш код, как я понимаю, потребует примерно 10000 итераций в худшем случае (в 60 раз больше), причём каждая итерация ещё и вычислительно тяжелее.

unsignedchar Oct 11 2021 at 23:15

Проверялась ли корректность работы алгоритма? Таблица первых нескольких млн простых чисел известна, можно сгенерировать свою и сравнить, например.

Проверялось ли быстродействие алгоритма по сравнению с другими аналогичными?

greabock Oct 11 2021 at 23:30

Уже одно то, что автор пытается спекулировать на десятичной системе счисления - говорит о серьезных проблемах в таком подходе. Числа они ведь не в курсе, что у нас десять пальцев. Они просто есть - без относительно того, как мы их записываем. Просто обратим внимание на то, какие числа он использует в этих спекуляциях:
1,2,3,5,7
Хм... как интересно. Да ведь они простые!
Возьмем систему счисления из 12 знаков (добавим a,b), и ву-а-ля - туда уже можно добавить b (11), и начать спекулировать еще и на нем. В общем... суть, я думаю, понятна. Эти эвристики строятся на системе записи. Но вот есть проблемка - человек, в принципе, не может считать быстрее компьютера. А компьютер считает нулями и единицами. В итоге, вы потеряете гораздо больше вычислительного времени на переводах чисел из двоичной системы в десятичную, чем получите выгоды от этих эвристик. Если бы у нас был компьютер с изначально десятичной системой, то эти эвристики имели бы место быть, и (уж поверьте) ими бы уже воспользовались.

masai Oct 12 2021 at 00:34

Уже одно то, что автор пытается спекулировать на десятичной системе счисления - говорит о серьезных проблемах в таком подходе.

Это не проблема. Когда мы рассматриваем последнюю цифру, то это просто вычисления по модулю 10. Ничего плохого в таком подходе самом по себе нет. Переход к вычислениям по модулю — это довольно частый приём при решении теоретико-числовых задач.

Например, одна из оптимизаций при проверке числа на простоту — это перебор делителей, у которых 1 или 5 в 6-ричной системе, и это даёт ускорение на 30 %, так как мы не рассматриваем цифру 3.

third112 Oct 12 2021 at 02:17

Мы знаем, что простые числа не четные

Нет:

Последовательность простых чисел начинается так:
2, 3, 5, 7

2 это единственное четное простое.