Возрастающие простые числа (ascending primes)

В этом примере мы реализуем алгоритм, который находит все простые числа, составленные из возрастающих цифр от 1 до 9.

Введение

Алгоритм поиска возсрастающих простых чисел предназначен для поиска всех простых чисел, которые можно составить, используя цифры от 1 до 9 в возрастающем порядке. Это означает, что каждая следующая цифра в числе не меньше предыдущей. Данный алгоритм используется для демонстрации работы с комбинаторикой и простыми числами в языке программирования Julia. Он находит применение в математических и олимпиадных задачах, где требуется найти определенные подмножества чисел.

# Установка необходимых пакетов
import Pkg; Pkg.add(["Combinatorics", "Primes", "BenchmarkTools"])

   Resolving package versions...
    Updating `~/.project/Project.toml`
  [6e4b80f9] + BenchmarkTools v1.6.0
    Updating `~/.project/Manifest.toml`
  [6e4b80f9] + BenchmarkTools v1.6.0
  [682c06a0] + JSON v0.21.4
  [69de0a69] + Parsers v2.8.3
  [a63ad114] + Mmap v1.11.0
  [9abbd945] + Profile v1.11.0

# Подключение необходимых библиотек
using Combinatorics  # Для работы с комбинаторными функциями (например, powerset)
using Primes         # Для проверки, является ли число простым
using BenchmarkTools # Для оценки времени выполнения

Основная часть

Функция `ascendingprimes()`

Эта функция генерирует все возможные непустые подмножества цифр от 1 до 9, преобразует их в числа и оставляет только простые числа. Рассмотрим работу по шагам.

# Определение функции ascendingprimes
function ascendingprimes()
    # Генерация всех возможных подмножеств множества [1, 2, 3, 4, 5, 6, 7, 8, 9]
    # powerset создает все возможные комбинации элементов множества, включая пустое множество
    # Мы фильтруем подмножества, оставляя только непустые (!isempty(x))
    # Затем для каждого подмножества:
    #   - reverse(x) разворачивает подмножество (например, [1,2,3] -> [3,2,1])
    #   - evalpoly(10, reverse(x)) вычисляет значение многочлена с основанием 10
    #     Это преобразует список цифр в число (например, [1,2,3] -> 321)
    #   - filter(isprime, ...) оставляет только простые числа
    return filter(isprime, [evalpoly(10, reverse(x)) for x in powerset([1, 2, 3, 4, 5, 6, 7, 8, 9]) if !isempty(x)])
end

ascendingprimes (generic function with 1 method)

Вывод результатов

Следующий код выводит найденные простые числа в форматированном виде, разбивая их по 10 чисел в строке.

# Вывод всех простых чисел в форматированном виде
# foreach применяет функцию к каждому элементу перечисления
# enumerate добавляет индексы к элементам списка
# rpad(p[2], 10) добавляет пробелы справа, чтобы число занимало 10 символов
# p[1] % 10 == 0 ? "\n" : "" - если индекс делится на 10, добавляется перевод строки
foreach(p -> print(rpad(p[2], 10), p[1] % 10 == 0 ? "\n" : ""), enumerate(ascendingprimes()))

2         3         5         7         13        17        19        23        29        37        
47        59        67        79        89        127       137       139       149       157       
167       179       239       257       269       347       349       359       367       379       
389       457       467       479       569       1237      1249      1259      1279      1289      
1367      1459      1489      1567      1579      1789      2347      2357      2389      2459      
2467      2579      2689      2789      3457      3467      3469      4567      4679      4789      
5689      12347     12379     12457     12479     12569     12589     12689     13457     13469     
13567     13679     13789     15679     23459     23567     23689     23789     25679     34589     
34679     123457    123479    124567    124679    125789    134789    145679    234589    235679    
235789    245789    345679    345689    1234789   1235789   1245689   1456789   12356789  23456789

Измерение времени выполнения

Последняя строка измеряет время выполнения функции ascendingprimes() с помощью макроса @btime.

# Измерение времени выполнения функции ascendingprimes()
@btime ascendingprimes()

  94.423 μs (3104 allocations: 173.75 KiB)

100-element Vector{Int64}:
        2
        3
        5
        7
       13
       17
       19
       23
       29
       37
       47
       59
       67
        ⋮
   234589
   235679
   235789
   245789
   345679
   345689
  1234789
  1235789
  1245689
  1456789
 12356789
 23456789

Заключение

В этом примере мы рассмотрели реализацию алгоритма поиска возрастающих простых чисел на языке Julia. Мы использовали пакет Combinatorics для генерации всех возможных подмножеств цифр от 1 до 9, а также пакет Primes для проверки простоты чисел. Нам удалось создать функцию, которая находит все простые числа, составленные из возрастающих цифр, и вывести их в удобочитаемом формате. Этот пример демонстрирует мощь языка Julia в области математических вычислений, комбинаторики и работы с простыми числами, что может быть полезно при решении различных математических задач и алгоритмических олимпиад.

Пример разработан с использованием материалов Rosetta Code

Возрастающие простые числа