升序素数
在这个例子中，我们正在实现一个算法，它找到由从1到9的递增数字组成的所有素数。
导言
搜索递增素数的算法旨在查找所有可以使用从1到9的数字按升序组成的素数。 这意味着数字中的每个后续数字不小于前一个数字。 该算法用于演示如何在Julia编程语言中使用组合数和素数。 它在数学和奥林匹克问题中找到应用，在这些问题中需要找到某些数字子集。
In [ ]:
# Установка необходимых пакетов
import Pkg; Pkg.add(["Combinatorics", "Primes", "BenchmarkTools"])
In [ ]:
# Подключение необходимых библиотек
using Combinatorics # Для работы с комбинаторными функциями (например, powerset)
using Primes # Для проверки, является ли число простым
using BenchmarkTools # Для оценки времени выполнения
主要部分
功能 ascendingprimes()
此函数生成从1到9的所有可能的非空位子集，将它们转换为数字，并仅留下素数。 让我们来看看工作一步一步。
In [ ]:
# Определение функции 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
Out[0]:
结果输出
下面的代码以格式化的形式输出找到的素数，每行将它们分成10个数字。
In [ ]:
# Вывод всех простых чисел в форматированном виде
# 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()))
测量执行时间
最后一行使用@btime宏测量ascendingprimes()函数的执行时间。
In [ ]:
# Измерение времени выполнения функции ascendingprimes()
@btime ascendingprimes()
Out[0]:
结论
在这个例子中，我们研究了Julia语言中搜索增加素数的算法的实现。 我们使用Combinatorics包生成从1到9的所有可能的数字子集，以及Primes包来检查数字的素数。 我们设法创建了一个函数，该函数查找由递增数字组成的所有素数，并以人类可读的格式输出它们。 这个例子展示了Julia语言在数学计算、组合学和处理素数方面的力量，这在解决各种数学问题和算法奥林匹克竞赛中是有用的。
该示例是使用[Rosetta代码]的材料开发的（https://rosettacode.org/wiki/Ascending_primes ）