PE Problem 95 Amicable chains （分解因子和）

电玩女神 2022-07-14 03:46 83阅读 0赞

## Amicable chains ##

### Problem 95 ###

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.

Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.

Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)

Since this chain returns to its starting point, it is called an amicable chain.

Find the smallest member of the longest amicable chain with no element exceeding one million.

代码：

转为Java选手....

import java.util.ArrayList;
    
    public class Main
    {
    	static int sum_Of_Divisors(int n)
    	{
    		int exclude = n;
    		int sum = 1;
    		for(int i = 2; (i * i) <= n; i++)
    		{
    			int p = 1;
    			while(n % i == 0)
    			{
    				p = p * i + 1;
    				n /= i;
    			}
    			sum *= p;
    		}
    		if(n > 1)
    			sum *= 1 + n;
    		return sum - exclude;
    	}
    	
    	static int findMin(ArrayList<Integer> list)
    	{
    		int min = list.get(0);//取下标为0的元素
    		for(int i = 1; i < list.size(); i++)
    			min = list.get(i) < min ? list.get(i):min;
    		return min;
    	}
    	
    	public static void main(String[] args)
    	{
    		int maxChain = 0;
    		int result = 0;
    		for(int i = 1; i < 1000000; i++)
    		{
    			ArrayList<Integer> amicableChains = new ArrayList<Integer>();
    			int n = i;
    			while(true)
    			{
    				amicableChains.add(n);//往链中增加元素n
    				n = sum_Of_Divisors(n); //分解因子和
    				if(n == i && amicableChains.size() > maxChain) //链是至今最长的
    				{
    					maxChain = amicableChains.size();
    					result = findMin(amicableChains);
    				}
    				if(amicableChains.contains(n) || n > 1000000)//回到起点或者n>1000000
    					break;
    			}
    		}
    		System.out.println(result);
    	}	
    }