Ascending primes
In this example, we are implementing an algorithm that finds all prime numbers made up of increasing digits from 1 to 9.
Introduction
The algorithm for searching for increasing primes is designed to find all the primes that can be composed using the numbers from 1 to 9 in ascending order. This means that each subsequent digit in the number is not less than the previous one. This algorithm is used to demonstrate how to work with combinatorics and prime numbers in the Julia programming language. It finds application in mathematical and Olympiad problems where it is required to find certain subsets of numbers.
# Установка необходимых пакетов
import Pkg; Pkg.add(["Combinatorics", "Primes", "BenchmarkTools"])
# Подключение необходимых библиотек
using Combinatorics # Для работы с комбинаторными функциями (например, powerset)
using Primes # Для проверки, является ли число простым
using BenchmarkTools # Для оценки времени выполнения
The main part
Function ascendingprimes()
This function generates all possible non-empty subsets of digits from 1 to 9, converts them to numbers, and leaves only prime numbers. Let's look at the work step by step.
# Определение функции 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
Conclusion of results
The following code outputs the found primes in formatted form, splitting them into 10 numbers per line.
# Вывод всех простых чисел в форматированном виде
# 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()))
Measuring the execution time
The last line measures the execution time of the ascendingprimes() function using the @btime macro.
# Измерение времени выполнения функции ascendingprimes()
@btime ascendingprimes()
Conclusion
In this example, we looked at the implementation of the algorithm for searching for increasing primes in the Julia language. We used the Combinatorics package to generate all possible subsets of digits from 1 to 9, as well as the Primes package to check the primality of numbers. We managed to create a function that finds all the prime numbers made up of increasing digits and outputs them in a human-readable format. This example demonstrates the power of the Julia language in mathematical calculations, combinatorics, and working with prime numbers, which can be useful in solving various mathematical problems and algorithmic Olympiads.
The example was developed using materials from Rosetta Code