亲和数、相亲数

转自：http://zh.wikipedia.org/wiki/%E7%9B%B8%E4%BA%B2%E6%95%B0

相亲数(Amicable Pair)，又称亲和数、友爱数，指两个正整数中，彼此的全部约数之和（本身除外）与另一方相等。


例如220与284：

    220的全部约数(除掉本身)相加是：1+2+4+5+10+11+20+22+44+55+110=284
    284的全部约数(除掉284本身)相加的和是：1+2+4+71+142=220

换句话说，亲和数又可以说成是两个正整数中，一方的全部约数之和与另一方的全部约数之和相等。

    220的全部约数之和是：1+2+4+5+10+11+20+22+44+55+110+220 = 284+220 = 504
    284的全部约数之和是：1+2+4+71+142+284 = 220+284 = 504

	public static void main(String[] args)
	{
		int n = 1000000;
		printLoveNumberGroup(n);
	}
	/**
	 * 相亲数(Amicable Pair)，又称亲和数、友爱数，指两个正整数中，彼此的全部约数之和（本身除外）与另一方相等。
	 * 
	 * http://zh.wikipedia.org/wiki/%E7%9B%B8%E4%BA%B2%E6%95%B0
	 * @param n
	 */
	public static void printLoveNumberGroup(int n)
	{
		int m = 2;
		Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
		do
		{
			List<Integer> list = findYueSu(m);
			int sum = getSum(list);
			
			List<Integer> list2 = findYueSu(sum);
			int sum2 = getSum(list2);
			if (m == sum)
			{
				System.out.println("self sum["+ m +"]");
			} else
			{
				if (m == sum2)
				{
					if (null == map.get(Integer.valueOf(m))) 
					{
						map.put(Integer.valueOf(sum), Boolean.TRUE);	
						System.out.println("love number["+ m +", "+ sum +"]");
					} 
				}
			}
			m++;
		} while (m <= n);
	}
	
	/**
	 * 查找被本身外的所有约数
	 * 
	 * @param n
	 * @return
	 */
	private static List<Integer> findYueSu(int n)
	{
		if (n < 1)
			return java.util.Collections.emptyList();
		
		List<Integer> list = new ArrayList<Integer>();
		list.add(Integer.valueOf(1));
		int mid = (int)Math.sqrt(n);
		for (int i = 2; i <= mid; i++)
		{
			int num = n/i;
			if (i * num == n)
			{
				list.add(Integer.valueOf(i));
				if (i != num)
				{
					list.add(Integer.valueOf(num));
				}
			}
		}
		return list;
	}
	
	private static int getSum(List<Integer> list)
	{
		int sum = 0;
		if (null == list || list.isEmpty())
		{
			return sum;
		}
		for (Integer num : list)
		{
			sum += num.intValue();
		}
		return sum;
	}