Amicable numbers efficient algorithm?

[Andi Rrashi]

Hi everyone,
I wrote this piece of code to find all pairs of amicable numbers.


Amicable numbers are two different numbers so related that the sum of the proper divisors of each is equal to the other number. For instance numbers


divisors of 220: 1, 2, 4, 5 ........, 55, 110
1+2+4+5+.........+55+110 = 284


divisors of 284: 1, 2, 4, 71, 142
1+2+4+71+142 = 220


This code works fine but if I test it with a limit value of 10000, it will take 3-4 seconds overall to calculate. For this limit value I need the calculation time to be below 2 seconds ... Does anyone know a more efficient algorithm that maybe skips some unnecessary calculations???


Thanks in advance!

#include <stdio.h>
#include <stdlib.h>


int main(int argc, char** argv) {
    
      int limit, n1, n2, chk;
      int counter = 220;
      
      printf("Enter limit:\n");
      scanf("%d", &limit);
      while (counter < limit)
      {
          int sum = 0;
          int div = 0;
          ++counter;
                    
          while (div <= counter/2)
          {
              ++div;
              if ( counter % div == 0 )
              sum += div;
          }
              chk = sum;
              sum = div = 0;
              
          while (div <= chk/2)
          {
              ++div;
              if ( chk % div == 0 )
              sum += div;
          }
              
          if ( sum == counter )
          {
              if ( counter == chk ) continue;
              n1 = counter;
                            
              if ( n1 == n2) continue;
              n2 = chk;
                            
              printf("%d, %d\n",n1,n2);
          }
      }
      return 0;
}

[anduril462]

I got about 0.17 seconds for your algorithm, with a limit of 10,000. Upping that limit to 100,000 took 15.490 seconds.

There are several things you can do to speed this up.

One simple thing is to take calculations out of loop conditions. Don't have your loops recompute counter/2 each time. Store that once in a temp variable before the loop and just do while (div < stop) for the loop.

A big improvement would be to use the square root of counter or chk as the stopping point of your loops, not counter/2 or chk/2. Every divisor greater than the square root has a pair less than the square root, so once you get to the square root, you've reached a "tipping" point. You can leverage the fact that if x is a divisor of n, then it's "pair" divisor is n/x, so your loop. That would make your loop look something like:

stop = (int) sqrt(counter);
while (div <= stop)
{
    if (counter % div == 0) {
        sum += div;  // add the divisor
        sum += counter / div;  // add the divisor's "pair"
    }
}

Another bit optimization would be to avoid the divisor check loops all together. You need to check for fail conditions as early as possible, before you loop through the possible divisors. If the sum of divisors of counter is equal to counter, then you will end up with an invalid "amicable pair", since both numbers will be the same (e.g. 496 forms a bogus amicable pair with itself). You can check for this after your first loop, skipping the second loop.

You also want to avoid redundant pairs, like 220,284 and 284,220. You already do this by keeping track of the sum of divisors of counter for the last amicable pair, and saying if (counter == chk) continue;. You can move that to the top of your outer loop and skip both internal loops, saving a ton of time. Note that you may need a few other minor tweaks when you make these last 2 changes.

I implemented these changes, and got run times of 0.02 seconds for a limit of 10,000 and 0.17 seconds for a limit of 100,000. That's nearly 10 times faster than your code on the small limit and nearly 100 times faster on the big limit!

[Andi Rrashi]

Hi anduril,

Thanks for your reply, it was pretty informative.

Now this may sound stupid but whenever I implement the sqrt(counter) I get no result at all displayed.

int stop = (int) sqrt(counter)
while (div <= stop)

If I substitute it with stop = counter/2 it works perfectly fine but not with the sqrt function. I implemented math library ....

[anduril462]

Strange. When I wrote my version, I used for loops, but that should hardly make a difference unless you don't set div to 0 in the right place. An uninitialized variable would result in undefined behavior, which may coincidentally make it "work" when you use counter/2 and not when you use sqrt. Can you post all of your new code?

[Andi Rrashi]

Yeah, I didn't implement all the fixes you suggested yet. I just modified this thing and here it is

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>


int main(int argc, char** argv) {
    
      clock_t start = clock();
    
      int limit, n1, n2, chk;
      int counter = 220;
      
      printf("Enter limit:\n");
      if (scanf("%d", &limit)!=1 || limit<=0)
      {
          printf("Invalid input.");
          return 0;
      }
      else 
      {
          while (counter < limit)
          {
              int sum = 0;
              int div = 0;
              counter++;


              int stop = (int) sqrt(counter);
              while (div <= stop)
              {
                  ++div;
                  if (counter % div == 0)
                  sum += div;                     
              }
                  chk = sum;
                  sum = div = 0;


              while (div <= chk/2)
              {
                  ++div;
                  if (chk % div == 0)
                  sum += div;
              }


              if (sum == counter)
              {
                  if (counter == chk) continue;
                  n1 = counter;


                  if (n1 == n2) continue;
                  n2 = chk;


                  printf("%d, %d\n",n1,n2);


              }
          }
      }
      printf("Time elapsed: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);
      return 0;
}

[anduril462]

    int counter = 220;


...
        while (counter < limit)
        {
            int sum = 0;
            int div = 0;
            counter++;

            int stop = (int) sqrt(counter);
            while (div <= stop)
            {
                ++div;
                if (counter % div == 0)
                    sum += div;
            }

You initialize counter to 220, then you increment it (counter++) before you ever check if it forms an amicable pair. This is why I prefer the for loop:

for (counter = 220; counter < limit; counter++)
{
    // do all your checks in here
}

Also, your loop that checks for divisors and adds them up isn't the one I showed you. Reread my original post and really think about why I did what I did there.

EDIT: I initialized sum to 1 in my version, and started div at 2.

[Andi Rrashi]

May I ask you a favor? If you still have the corrected version of the code may you post it here? I know that this is not the purpose of a forum essentially but you would really do me a great favor.

[anduril462]

No can do. It's not just an issue of the forum's purpose, it has to do with academic integrity, and making sure you actually learn to program, not just copy and paste. I'll give you a nudge with some pseudo code:

for counter from 220 to limit
    sum1 = 1  // initialize sum for the first number
    stop = sqrt(counter)
    for i from 2 to <= stop
        check for divisibility by i and add the pair of divisors to sum1

    sum2 = 1  // initialize sum for the second number
    stop = sqrt(sum1)
    for i from 2 to <= stop
        check for divisibility by i and add the pair of divisors to sum2

Hopefully that will get you going in the right direction. Note that what goes in the internal for loops is essentially what went in the while loop I gave you in post #2.

[Andi Rrashi]

OK, I'll be working on it, I got the basic idea from the pseudo code though ... Once again thanks, I really appreciate that you took your time to answer to this post.

[anduril462]

You're welcome.

[Jimmy998]

I've just come across this thread and I'd quite like to get it going as well but I can't figure out how to implement conditions from anduril462's last post into the original code. Could you possibly re-explain where do you put the for-cycles? I'd be really grateful for that.

[Adak]

The for loops in post #8 of the thread, should replace the while loops in post #6.

Much more importantly, what is stopping you from coding up this problem?

[Jimmy998]

Did I do it right? I think I messed up something with if-conditions, but I'm not quite sure what.

for (counter = 220; counter < limit; counter++)
        {
            sum1 = 1;
            int stop1 = sqrt(counter);
            for (i = 2; i <= stop1; i++)
            {
                if (counter % i == 0)
                {
                sum1 += i;
                sum1 += counter / i;
                }
            }



            sum2 = 1;
            int stop2 = sqrt(sum1);
            for (i = 2; i <= stop2; i++)
            {
                if (counter % i == 0)
                {
                sum2 += i;
                sum2 += counter / i;
                }
            }
        }

I'm a beginner and we had a similar problem at school so I would really love to get this going, but right now I'm still lost in speeding it up as said above

[Salem]

> And I'm sorry, but I can't even post the code properly as it's done above.
You need to paste "as text" not "as HTML".

[Jimmy998]

Thank you Salem I somewhat made it. But I still can't figure out how should I implement the if-conditions so that it does what it's supposed to do.