#include <iostream>
#include <cassert>

const int maxprime = 65536;

int primes[maxprime];
int nprimes;

void findPrimes() {
    std::cout << "Searching prime numbers ..." << std::endl;
    bool *sieve = new bool[maxprime+1];
    int i;
    for (i=0;i<maxprime;i++)
        sieve[i] = 0;
    i = 2;
    nprimes = 0;
    while (1) {
        while (i<maxprime && sieve[i])
            i++;
        if (i>=maxprime)
            break;
        primes[nprimes++] = i;
        for (int j=i*2; j<maxprime; j+=i)
            sieve[j] = 1;
        i++;
    }
    std::cout << nprimes << " primes found" << std::endl;
    delete sieve;
}

int sumDiv(int a) {
    int i, r=1, b=a;
    int *pr = primes;
    while (b > 1) {
        int p = *pr++, s = 1;
        if (p*p > b)
            return r * (b+1) - a;
        while (b % p == 0) {
            b /= p;
            s = s*p + 1;
        }
        r *= s;
    }
    return r;
}

int main() {
    findPrimes();
    int cnt = 0;
    for (int a=1; ; a++) {
        int b = sumDiv(a);
        if (a < b && sumDiv(b) == a) {
            cnt++;
            std::cout << cnt << " (" << a << ", " << b << ")" << std::endl;
            if (cnt == 60)
                break;
        }
    }
    return 0;
}