11.10.2021 19:33
kurduk 26 5600 Источник

Простых чисел бесконечное множество. В интернете в свободном доступе можно найти таблицы простых чисел до 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)


  1. VolodjaT
    11.10.2021 19:43
    #23579570
    +2

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

    Это почему? Что мешает написать длинную арифметику на VB?


    1. kurduk Автор
      11.10.2021 21:41
      #23579966

      Возможно мои познания в программировании, а над "длинной арифметикой" я подумаю на досуге.


      1. VolodjaT
        12.10.2021 02:07
        #23580704

        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 уже давно есть готовая библиотека


  1. fougasse
    11.10.2021 19:49
    #23579596
    +2

    Не «до 21000000», а 21 миллион простых чисел, наверное?

    Ибо с определением простоты до 21M никаких проблем, вообще, не предвидится.

    Ну и код скриншотом - почему?


    1. GerrAlt
      11.10.2021 21:13
      #23579860
      +1

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


      1. GeMir
        11.10.2021 21:31
        #23579926
        +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 не знаком вообще и судя по синтаксису — к счастью.


      1. kurduk Автор
        12.10.2021 11:57
        #23582060
        +2

        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


        1. unsignedchar
          12.10.2021 12:20
          #23582160

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


        1. domix32
          12.10.2021 13:17
          #23582512
          +3

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

          ```vbscript
dim some code
````

          для легаси html 
          <source lang="vbscript">
dim some code
&lt/source>


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

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


  1. yaguarundi
    11.10.2021 19:57
    #23579642

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


  1. lorc
    11.10.2021 19:57
    #23579644
    +3

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

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


    1. ZodDZverev
      11.10.2021 20:58
      #23579810

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

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

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


      1. lorc
        11.10.2021 21:42
        #23579974

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

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


      1. kurduk Автор
        11.10.2021 21:56
        #23580024

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

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

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


        1. Politura
          12.10.2021 09:23
          #23581208
          +1

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

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

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


          1. kurduk Автор
            12.10.2021 12:36
            #23582256
            +1

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


    1. lightln2
      11.10.2021 21:58
      #23580036
      +1

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

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


  1. casuss
    11.10.2021 21:02
    #23579816
    +1

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

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


    1. kurduk Автор
      11.10.2021 21:36
      #23579954
      +1

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


    1. kurduk Автор
      11.10.2021 21:43
      #23579978

      Это опечатка


  1. Scratch
    11.10.2021 21:45
    #23579982
    +4

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

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


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


  1. unsignedchar
    11.10.2021 23:15
    #23580266
    +1

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

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


  1. greabock
    11.10.2021 23:30
    #23580320
    +3

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


    1. masai
      12.10.2021 00:34
      #23580528
      +2

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

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

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


  1. third112
    12.10.2021 02:17
    #23580714
    +1

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

    Нет:


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

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