Two integers 



N


{\displaystyle N}

 and 



M


{\displaystyle M}

 are said to be amicable pairs if 



N
≠
M


{\displaystyle N\neq M}

 and the sum of the proper divisors of 



N


{\displaystyle N}

 (




s
u
m

(

p
r
o
p
D
i
v
s

(
N
)
)


{\displaystyle \mathrm {sum} (\mathrm {propDivs} (N))}

) 



=
M


{\displaystyle =M}

 as well as 




s
u
m

(

p
r
o
p
D
i
v
s

(
M
)
)
=
N


{\displaystyle \mathrm {sum} (\mathrm {propDivs} (M))=N}

.



Example

1184 and 1210 are an amicable pair, with proper divisors:

   1, 2, 4, 8, 16, 32, 37, 74, 148, 296, 592   and 
   1, 2, 5, 10, 11, 22, 55, 110, 121, 242, 605   respectively.


Task

Calculate and show here the Amicable pairs below 20,000; (there are eight).



Related tasks
 Proper divisors
 Abundant, deficient and perfect number classifications
 Aliquot sequence classifications and its amicable classification. 


#include <stdio.h>
#include <stdlib.h>
 
typedef unsigned int uint;
 
int main(int argc, char **argv)
{
  uint top = atoi(argv[1]);
  uint *divsum = malloc((top + 1) * sizeof(*divsum));
  uint pows[32] = {1, 0};
 
  for (uint i = 0; i <= top; i++) divsum[i] = 1;
 
  // sieve
  // only sieve within lower half , the modification starts at 2*p
  for (uint p = 2; p+p <= top; p++) {
    if (divsum[p] > 1) {
      divsum[p] -= p;// subtract number itself from divisor sum ('proper')
      continue;}     // p not prime
 
    uint x; // highest power of p we need
    //checking x <= top/y instead of x*y <= top to avoid overflow
    for (x = 1; pows[x - 1] <= top/p; x++)
      pows[x] = p*pows[x - 1];
 
    //counter where n is not a*p with a = ?*p, useful for most p.
    //think of p>31 seldom divisions or p>sqrt(top) than no division is needed
    //n = 2*p, so the prime itself is left unchanged => k=p-1
    uint k= p-1;
    for (uint n = p+p; n <= top; n += p) {
      uint s=1+pows[1];
      k--;
      // search the right power only if needed
      if ( k==0) {
        for (uint i = 2; i < x && !(n%pows[i]); s += pows[i++]);
        k = p; }
      divsum[n] *= s;
    }
  }
 
  //now correct the upper half
  for (uint p = (top >> 1)+1; p <= top; p++) {
    if (divsum[p] > 1){
      divsum[p] -= p;}
  }
 
  uint cnt = 0;
  for (uint a = 1; a <= top; a++) {
    uint b = divsum[a];
    if (b > a && b <= top && divsum[b] == a){
      printf("%u %u\n", a, b);
      cnt++;}
  }
  printf("\nTop %u count : %u\n",top,cnt);
  return 0;
}