Engee 文档
Notebook

互质数

此示例检查了Coprimes的Julia搜索算法的实现，该算法过滤数字集，只留下所有数字都是coprimes（它们的节点为1）的数字集。

导言

搜索互质数组的算法解决了过滤数组的问题，只留下所有数都是互质数的数组。 互质数是最大公约数（GCD）为1的数字。 这些数字集用于密码学，数论以及与分数和模块化算术相关的算法。

主要部分

数据准备

首先，我们定义一组数字列表，我们将检查互素性。 每个子列表是一组数字，我们要检查的节点。

In [ ]: 
# 源数据：一组数字列表
data = [[21,15],[17,23],[36,12],[18,29],[60,15],[21,22,25,31,143]]
Out[0]:
6-element Vector{Vector{Int64}}:
 [21, 15]
 [17, 23]
 [36, 12]
 [18, 29]
 [60, 15]
 [21, 22, 25, 31, 143]

现在让我们对这些数据应用过滤。 为此，请使用函数 filter，这将只留下满足条件的那些集合：集合中所有数字的最大公约数为1。

In [ ]: 
# 过滤：我们只留下所有数字的节点为1的集合
# p是一组数字（例如，[21,15]）
# gcd（p。..）-计算集合中所有数字的节点，通过"splat"（。..)

coprime_sets = filter(p -> gcd(p...) == 1, data)
Out[0]:
3-element Vector{Vector{Int64}}:
 [17, 23]
 [18, 29]
 [21, 22, 25, 31, 143]

我们来分析一下表达式 gcd(p...) 更详细:

  • p —这是一个数字数组，例如, [21, 15].
  • p... —这是"splat"运算符，它将数组扩展为单独的参数。 这就是 gcd([21, 15]...) 变成 gcd(21, 15).
  • gcd -Julia计算最大公约数的标准函数。

工作的结果

作为算法的结果，我们得到了一个列表，其中所有数字都是coprime的那些数字集。 相互简单意味着集合中所有数字的节点为1。

In [ ]: 
# 结果的输出
println("相互简单的集合:")
for set in coprime_sets
    println(set)
end

Взаимно простые наборы:
[17, 23]
[18, 29]
[21, 22, 25, 31, 143]

结论

在这个例子中，我们实现了一个搜索互质数组的算法，它过滤了数组，只留下所有数都是互质数的数组。 这在数字没有公共除数很重要的任务中很有用，例如在密码学中或在使用分数时。 我们使用了Julia的内置函数: filter, gcd 和运营商 ... 解开论点。

该示例是使用[Rosetta代码]的材料开发的（https://rosettacode.org/wiki/Coprimes ）