import java.util.HashSet;
import java.util.Set;


public class Divisors {

	Set[] d;
	int[] s;
	int n;

	public Divisors(int n)	{

		this.n = n;
		d = new Set[n + 1];
		s = new int[n + 1];

		for (int i = 1; i <= n; i++)	{
			d[i] = new HashSet();
		}

		for (int i = 1; i <= n; i++)	{
			seive(i);
		}
	}

	private void seive(int toSeive) throws IllegalArgumentException	{

		if (toSeive < 1)	{
			throw new IllegalArgumentException();
		}

		for (int i = toSeive; i <= n; i+=toSeive)	{
			if (d[i].add(new Integer(toSeive)) && i!=toSeive)	{
				s[i] += toSeive;
			}
		}
	}

	private void printD()	{

		for (int i = 1; i <= n; i++)	{
			System.out.println(i + ": " + d[i] + " Sum: " + s[i]);
		}
	}

	private void computePerfectsAndPairs()	{

		for (int i = 1; i <= n; i++)	{
			if (s[i] == i)	{
				System.out.println("Perfect number " + i + ": " + d[i]);
			}

			if (s[i] > 0 && s[i] <= n && i < s[i] && i == s[s[i]])	{
				System.out.println("Amicable pair " + i + " and " + s[i]
					+ ": " + d[i] + " " + d[s[i]]);
			}
		}
	}

	public static void main(String[] args)	{

		Divisors d = new Divisors(10000);
	//	d.printD();
		d.computePerfectsAndPairs();
	}
}


Perfect number 6: [1, 2, 3, 6]
Perfect number 28: [1, 2, 4, 7, 28, 14]
Amicable pair 220 and 284: [220, 1, 2, 55, 4, 20, 5, 22, 110, 10, 11, 44] [1, 2, 71, 4, 142, 284]
Perfect number 496: [16, 1, 2, 4, 248, 8, 124, 496, 62, 31]
Amicable pair 1184 and 1210: [592, 16, 1, 32, 2, 1184, 4, 37, 296, 8, 148, 74] [1, 2, 55, 5, 22, 1210, 110, 10, 11, 605, 242, 121]
Amicable pair 2620 and 2924: [1, 655, 2, 262, 4, 1310, 20, 5, 524, 131, 10, 2620] [68, 34, 17, 1, 2, 731, 86, 4, 1462, 172, 43, 2924]
Amicable pair 5020 and 5564: [1255, 2510, 1, 2, 5020, 4, 1004, 251, 20, 5, 502, 10] [1, 2, 1391, 4, 428, 2782, 52, 214, 26, 5564, 107, 13]
Amicable pair 6232 and 6368: [1, 2, 4, 38, 8, 76, 41, 6232, 164, 152, 19, 3116, 82, 1558, 779, 328] [16, 1, 32, 2, 4, 398, 1592, 8, 199, 796, 6368, 3184]
Perfect number 8128: [508, 1016, 2032, 1, 4064, 8128, 2, 32, 4, 64, 8, 254, 16, 127]