数据结构和算法 数论 亲密数

1、什么是亲密数？

        亲密数(Amicable Numbers)，是具有特殊性质的整数。亲密数展示了两个整数之间通过因子的密切联系。

        如果整数a的因子和等于整数b，整数b的因子和等于整数a，因子包括1但不包括本身，且a不等于b，则称a、b为亲密数。

        例如，220和284便是一对亲密数，满足如下规则。

        220的各个因子之和为：1+2+4+5+10+11+20+22+44+55+110=284；

        284的各个因子之和为：1+2+4+71+142=220。

        另外，1184和1210是一对亲密数，因为其满足如下规则：

        1210的各个因子之和为：1+2+5+10+11+22+55+110+121+242+605=1184。

2、找出数组中成对的亲密数

        给定数组，[220, 284, 1184,1210, 2, 5]，找到其中成对的亲密数。

（1）c++

#include <bits/stdc++.h>
using namespace std;

int sumOfDiv(int x)
{
	// 1 是因子
	int sum = 1;
	for (int i = 2; i <= sqrt(x); i++)
	{
		if (x % i == 0) {
			sum += i;

			if (x / i != i)
				sum += x / i;
		}
	}
	return sum;
}

bool isAmicable(int a, int b)
{
	return (sumOfDiv(a) == b &&
			sumOfDiv(b) == a);
}

int countPairs(int arr[], int n)
{
	unordered_set<int> s;
	int count = 0;
	for (int i = 0; i < n; i++)
		s.insert(arr[i]);


	for (int i = 0; i < n; i++)
	{
		if (s.find(sumOfDiv(arr[i])) != s.end())
		{
			int sum = sumOfDiv(arr[i]);
			if (isAmicable(arr[i], sum))
				count++;
		}
	}


	return count / 2;
}

int main()
{
	int arr1[] = { 220, 284, 1184,
				1210, 2, 5 };
	int n1 = sizeof(arr1) / sizeof(arr1[0]);
	cout << countPairs(arr1, n1)
		<< endl;
	
	int arr2[] = { 2620, 2924, 5020,
				5564, 6232, 6368 };
	int n2 = sizeof(arr2) / sizeof(arr2[0]);
	cout << countPairs(arr2, n2)
		<< endl;
	return 0;
}

（2）java

import java.io.*;

class GFG
{

	static int sumOfDiv(int x)
	{

		// 1 是因子
		int sum = 1;
		for (int i = 2; i <= Math.sqrt(x); i++)
		{
			if (x % i == 0)
			{
				sum += i;

				// To handle perfect squares
				if (x / i != i)
					sum += x / i;
			}
		}

		return sum;
	}

	static boolean isAmicable(int a, int b)
	{
		return (sumOfDiv(a) == b &&
				sumOfDiv(b) == a);
	}

	static int countPairs(int arr[], int n)
	{
		int count = 0;
		for (int i = 0; i < n; i++)
			for (int j = i + 1; j < n; j++)
				if (isAmicable(arr[i], arr[j]))
					count++;

		return count;
	}


	public static void main(String args[])
	{

		int arr1[] = { 220, 284, 1184,
					1210, 2, 5 };
		int n1 = arr1.length;

		System.out.println(countPairs(arr1, n1));

		int arr2[] = { 2620, 2924, 5020,
					5564, 6232, 6368 };
		int n2 = arr2.length;

		System.out.println(countPairs(arr2, n2));
	}
}

（3）python

# 计算因子和
def sumOfDiv(x):
	sum = 1
	for i in range(2, x):
		if x % i == 0:
			sum += i
	return sum

# 检查对是否友好
def isAmicable(a, b):
	if sumOfDiv(a) == b and sumOfDiv(b) == a:
		return True
	else:
		return False


def countPairs(arr, n):
	count = 0
	for i in range(0, n):
		for j in range(i + 1, n):
			if isAmicable(arr[i], arr[j]):
				count = count + 1
	return count


arr1 = [220, 284, 1184, 1210, 2, 5]
n1 = len(arr1)
print(countPairs(arr1, n1))

arr2 = [2620, 2924, 5020, 5564, 6232, 6368]
n2 = len(arr2)
print(countPairs(arr2, n2))

（4）c#

using System;

class Amicable
{
	static int sumOfDiv(int x)
	{
		
		// 1 is a proper divisor
		int sum = 1;
		for (int i = 2; i <= Math.Sqrt(x); i++)
		{
			if (x % i == 0)
			{
				sum += i;

				// To handle perfect squares
				if (x / i != i)
					sum += x / i;
			}
		}
		
		return sum;
	}


	static bool isAmicable(int a, int b)
	{
		return (sumOfDiv(a) == b &&
				sumOfDiv(b) == a);
	}


	static int countPairs(int []arr, int n)
	{
		int count = 0;

		for (int i = 0; i < n; i++)
		
			for (int j = i + 1; j < n; j++)
				if (isAmicable(arr[i], arr[j]))
					count++;

		return count;
	}


	public static void Main()
	{

		int []arr1 = {220, 284, 1184,
					1210, 2, 5};
		int n1 = arr1.Length;
		
		Console.WriteLine(countPairs(arr1, n1));

		int []arr2 = {2620, 2924, 5020,
					5564, 6232, 6368};
		int n2 = arr2.Length;

		Console.WriteLine(countPairs(arr2, n2));
	}
}

（5）php

<?php
function sumOfDiv( $x)
{
	// 1 is a proper divisor
	$sum = 1;
	for ( $i = 2; $i <= sqrt($x); $i++)
	{
		if ($x % $i == 0)
		{
			$sum += $i;

			if ($x / $i != $i)
				$sum += $x / $i;
		}
	}
	return $sum;
}

function isAmicable( $a, $b)
{
	return (sumOfDiv($a) == $b and
			sumOfDiv($b) == $a);
}

function countPairs( $arr, $n)
{
	$count = 0;

	for ( $i = 0; $i < $n; $i++)
		for ( $j = $i + 1; $j < $n; $j++)
			if (isAmicable($arr[$i], $arr[$j]))
				$count++;

	return $count;
}

$arr1 = array( 220, 284, 1184, 1210, 2, 5 );
$n1 = count($arr1);
echo countPairs($arr1, $n1),"\n";

$arr2 = array( 2620, 2924, 5020, 5564, 6232, 6368 );
$n2 = count($arr2);
echo countPairs($arr2, $n2);

// This code is contributed by anuj_67.
?>

（6）javascript

<script>
	function sumOfDiv(x)
	{
		let sum = 1;
		for (let i = 2; i <= Math.sqrt(x); i++)
		{
			if (x % i == 0)
			{
				sum += i;

				if (parseInt(x / i, 10) != i)
					sum += parseInt(x / i, 10);
			}
		}
		
		return sum;
	}

	// Check if pair is amicable
	function isAmicable(a, b)
	{
		return (sumOfDiv(a) == b &&
				sumOfDiv(b) == a);
	}


	function countPairs(arr, n)
	{
		let count = 0;

		// Iterate through each pair,
		// and find if it an amicable pair
		for (let i = 0; i < n; i++)
		
			for (let j = i + 1; j < n; j++)
				if (isAmicable(arr[i], arr[j]))
					count++;

		return count;
	}
	
	let arr1 = [220, 284, 1184, 1210, 2, 5];
	let n1 = arr1.length;

	document.write(countPairs(arr1, n1) + "</br>");

	let arr2 = [2620, 2924, 5020, 5564, 6232, 6368];
	let n2 = arr2.length;

	document.write(countPairs(arr2, n2));
	
</script>