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]