确定友好数字（友好对）的算法
我们正在考虑实现一种算法，用于搜索高达给定限制的友好数字对。
导言
什么是友好号码？
友好数字是两个自然数，使得一个数字的适当除数的总和等于另一个数字，反之亦然。 例如，一对夫妇 它很友好:
\是它自己的除数的总和
\是它自己的除数的总和
让我们开发一个算法，找到所有这些对达到指定的限制。
主要部分
在使用外部软件包之前，您需要安装它。:
import Pkg; Pkg.add("Primes")
连接必要的库:
using Primes, Printf # Primes для проверки простоты чисел, Printf для форматированного вывода
计算素数乘数贡献的函数
此函数计算素数的幂的总和。 从度 以前 .
function pcontrib(p::Int64, a::Int64)
n = one(p) # Начинаем с p^0 = 1
pcon = one(p) # Инициализация суммы значением 1 (p^0)
for i in 1:a # Для каждой степени от 1 до a
n *= p # Увеличиваем степень p: p^i
pcon += n # Добавляем p^i к сумме
end
return pcon # Возвращаем сумму: 1 + p + p^2 + ... + p^a
end
函数操作说明 pcontrib:
要计算一个数字的所有除数的总和，必须考虑到如果数字具有规范分解 ，那么它的所有除数的总和将等于产品:
功能 pcontrib 为特定素因子计算一个这样的括号。
计算所有除数之和的函数
使用其素因式分解计算数的所有除数的总和。
function divisorsum(n::Int64)
dsum = one(n) # Начальное значение произведения - 1
for (p, a) in factor(n) # Для каждого простого множителя p степени a в разложении n
dsum *= pcontrib(p, a) # Домножаем на сумму (1 + p + p^2 + ... + p^a)
end
dsum -= n # Вычитаем само число, чтобы получить сумму только собственных делителей
end
功能说明 divisorsum:
使用算术的基本定理-每个自然数都可以表示为素数幂的乘积（规范分解）。 通过系数的乘积计算所有除数的总和 pcontrib. 然后从这个数量中减去数字本身。 以获得仅其自身除数的总和（小于数字本身）。
寻找友好夫妇的主要功能
主要功能，搜索所有对友好的数字达到极限。
function amicables(L = 2*10^7) # Поиск пар до значения L (по умолчанию 20 миллионов)
acnt = 0 # Счетчик найденных пар
# Вывод информационного сообщения
println("Amicable pairs not greater than ", L)
# Перебираем все числа от 2 до L
for i in 2:L
!isprime(i) || continue # Пропускаем простые числа (у них сумма собственных делителей всегда 1)
j = divisorsum(i) # Вычисляем сумму собственных делителей числа i
# Проверяем условие дружественности:
# - j должен быть меньше i (чтобы не повторяться)
# - сумма собственных делителей j должна быть равна i
j < i && divisorsum(j) == i || continue
# Если пара найдена, увеличиваем счетчик и выводим результат
acnt += 1
println(@sprintf("%4d", acnt), " => ", j, ", ", i)
end
end
函数中优化的解释 amicables:
循环从 以前 按升序排列。
支票 确保每对只找到一次，即如果一对已经见过面。 然后它将不再输出为 . 素数也被跳过，因为素数的适当除数之和是 ，而 永远无法形成友好的一对。
amicables() # Запуск поиска с параметрами по умолчанию (до 20,000,000)
程序的结果将包含一个升序排列的友好数字对列表，其中第一个数字小于第二个。
输出格式: <порядковый_номер> => <меньшее_число>, <большее_число>
结论
我们回顾了友好数字搜索算法在Julia编程语言中的实现。
该算法利用将数字分解为素数因子的数学属性来有效地计算它们自己的除数之和。 效率是通过使用数论而不是直接通过所有除数来实现的。 该程序查找到指定限制的所有友好对，并用编号输出它们。 这种方法在数论和娱乐数学中有实际应用。 有趣的是，古希腊人知道友好的数字，最小的一对（220,284）是毕达哥拉斯发现的。
该示例是使用[Rosetta代码]的材料开发的（https://rosettacode.org/wiki/Amicable_pairs ）