5
\$\begingroup\$

I took it as a challenge to write a C++ program to find the first 10 amicable-numbers.

Amicable numbers

Let's take 4. What are the proper divisors of 4?. They are 1 and 2. Their sum is: 3.

Now let's do the same thing for the number 220. The sum of the proper divisors of 220 is: 284 The sum of proper divisors of the number 284 is:220

Hence they are amicable.

If the sum of proper divisors of two numbers are equal to each other then they are amicable. For example 284 and 220 The sums of their proper factors are equal to 220 and 284 respectively. Hence, they are amicable.

This is my c++ program to find the first 10 amicable numbers

#include<iostream>

int GetSumOfFactors(int num){
    int sum = 0;
    for(int i = 1;i < num/2+1;i++){
        if(num % i==0){
            sum+=i;
        }
    }
    return sum;
}
int main(){
    int sum_of_factors = 0;
    int counter = 0;
    int num = 0;
    for(;;){
        num++;
        sum_of_factors = GetSumOfFactors(num);
        if(num == sum_of_factors) continue;
        if (GetSumOfFactors(sum_of_factors) == num && num > sum_of_factors){
            std::cout << "Pair: " << num << " " << sum_of_factors << "\n";
            counter+=1;
        }
        if(counter == 10) break;
    }
    return 1;
}

To make sure I don't find the same pair twice, that means 220 to 284, just like 284 to 220. I keep an extra condition where the number should be greater than it's sum of factors.

Output:

Pair: 284 220
Pair: 1210 1184
Pair: 2924 2620
Pair: 5564 5020
Pair: 6368 6232
Pair: 10856 10744
Pair: 14595 12285
Pair: 18416 17296
Pair: 66992 66928
Pair: 71145 67095

Process returned 1 (0x1)   execution time : 4.955 s
Press any key to continue.
\$\endgroup\$
3
\$\begingroup\$

I'll add some remarks (adding to what Miguel Avila already said) and then focus on the performance aspect.

  • Use consistent naming: you mix camel case (FactorsSum) and snake case (sum_of_factors).
  • Use consistent spacing (after keywords like if and around operators).
  • Declare variables and the narrowest possible scope. As an example, sum_of_factors is only needed inside the for-loop.
  • Use proper exit codes. A non-zero exit code indicates the failure of a program. You'll want to return 0; or return EXIT_SUCCESS;. In fact you can simply omit the return statement: Reaching the end of main() does an implicit return 0; in C++.

If you care about portability: C++ does not specify the size of int, only its minimum range (which is -32767 to 32767). You should use long (with a minimum range -2147483647 to 2147483647) or one of the fixed-size types (int32_t or int64_t) depending on the needed range.

Performance improvement #1

Computing the sum of all (proper) divisors of a number can be significantly improved by observing that if \$ i \$ divides \$ n \$ then both \$ i \$ and \$ n/i \$ are divisors of \$ n\$. Therefore it suffices to test all \$ i \le \sqrt n\$. See for example Sum of all proper divisors of a natural number. A possible implementation is

// Returns the sum of all proper divisors of `n`.
int divisor_sum(int n) {
    if (n <= 1) {
        return 0;
    }
    
    int count = 1; // 1 is always a divisor.
    int sqrt_n = (int)sqrt(n); // Upper bound for the loop.
    for (int i = 2; i <= sqrt_n; i++) {
        if (n % i == 0) {
            // `i` and `n / i` are divisors of `n`.
            count += i;
            if (i !=  n / i) {
                count += n / i;
            }
        }
    }
    return count;
}

Performance improvement #2

In your main loop, you compute the divisor sum of sum_of_factors even if that is larger than num:

if (GetSumOfFactors(sum_of_factors) == num && num > sum_of_factors)

A simple improvement would be to change the order of the expressions:

if (num > sum_of_factors && GetSumOfFactors(sum_of_factors) == num)

Another option is to remember the divisor sums of numbers which are possible candidates of an amicable pair, so that they need not be computed again. This can for example be done with a

std::unordered_map<int, int> abundant_divsums;

which holds all abundant numbers with their divisor sums encountered so far. A number is abundant if its proper divisor sum is larger than the number. These are candidates for an amicable pair with higher numbers.

A possible implementation is

#include <unordered_map>

int main()
{
    std::unordered_map<int, int> abundant_divsums;
    
    int num = 1;
    for (int counter = 0; counter < 10; num++) {
        int divsum = divisor_sum(num);
        if (divsum > num) {
            abundant_divsums[num] = divsum;
        } else if (divsum < num) {
            if (abundant_divsums.find(divsum) != abundant_divsums.end() && abundant_divsums[divsum] == num) {
                std::cout << "Pair: " << num << ' ' << divsum << '\n';
                counter++;
            }
        }
    }
}

Benchmarks

The tests were done on a MacBook Air (1.1 GHz Quad-Core Intel Core i5), with the code compiled with optimizations (“Release” configuration).

I measured the time for computing the first 10/20/50 amicable pairs. All times are in seconds.

# of amicable pairs:    10      20      50
------------------------------------------
Original code:          3.8     24
After improvement #1:   0.08    0.2     3.8
After improvement #2:   0.05    0.15    2.5
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @superbrain: I simply used the time command line utility on macOS. – abundant_divsums.count(divsum) made no significant difference in my tests. Just abundant_divsums[divsum] == num without checking for the existence of the key will insert { divsum, 0 } if it does not exist. That made it slightly slower in my tests, probably because of the increase in size of the hash map. \$\endgroup\$ – Martin R Sep 6 at 0:16
  • \$\begingroup\$ @superbrain: Computing the divisor function from the prime factorization is indeed faster (~1 second for 50 pairs). \$\endgroup\$ – Martin R Sep 6 at 0:34
  • \$\begingroup\$ That is a huge improvement!, I knew about the square root rule for the natural number but wasn't 100 % sure, do I need to include any library for that function? \$\endgroup\$ – Aryan Parekh Sep 6 at 3:40
  • \$\begingroup\$ You can also add this: The pair is always even and even or odd and odd. That means the sum_of_factors and num is always the same. either both are even or both are odd, will this speed up the program? \$\endgroup\$ – Aryan Parekh Sep 6 at 4:11
  • \$\begingroup\$ @superbrain: Good catch. It does not affect the search for amicable pairs, but should be fixed of course (done). Thanks for the feedback! \$\endgroup\$ – Martin R Sep 6 at 11:31
4
\$\begingroup\$

There are few aspects which I will touch.

  • The function GetSumOfFactors could be renamed as FactorsSum, it is done to simplify the reading.
  • You are declaring a for loop for(;;) (equivalent to while (true)) but that is quite bad, one generally includes the ending statement in the for, as the variables updates and, if used only there, for loop scoped variables.
  • You are sending " " and "\n" to the cout variable, it depends on the interpretation the compiler will do but primarily it is interpreted as a const char* variable, it would be better to use '\n' and ' ' which are char variables.
  • Try to not use break if it depends on a verifiable condition each iteration, put the equivalent condition in the for statement.

Finally, a tip which I consider not as optimization in the coding aspect but is useful is to use -O3 when compiling your code (works for g++), this is a flag which tells the compiler to optimize output.

Specifically your code could be written as:

#include <iostream>

int FactorsSum(int num)
{
    int sum = 0;
    for (int i = 1; i < num / 2 + 1; i++)
        if (num % i == 0) sum += i;
    return sum;
}

int main()
{
    int sum_of_factors = 0;
    int num = 0;
    for (int counter = 0; counter < 10; num++)
    {
        sum_of_factors = FactorsSum(num);
        if (num != sum_of_factors && FactorsSum(sum_of_factors) == num && num > sum_of_factors)
        {
            std::cout << "Pair: " << num << ' ' << sum_of_factors << '\n';
            counter++;
        }
    }
    return 0x0;
}

Note that num != sum_of_factors is equivalent to end the if in the case num == sum_of_factors be true, so that you can omit the continue instruction.

I hope it was of help.

(Thanks to Martin R for his comment. Now I have tested this program and it works as intended)

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Note that your program does not print the first 10 amicable pairs. In fact it prints nothing. The reason is that counter is increased in every loop iteration, no matter if an amicable number is found or not. – Also returning a non-zero exit code does normally indicate an error. \$\endgroup\$ – Martin R Sep 5 at 15:53
  • 1
    \$\begingroup\$ Yes I fixed that error, ig I corrected it in the main code and forgot to correct it here, I apologize for that ✌ \$\endgroup\$ – Aryan Parekh Sep 5 at 17:28
2
\$\begingroup\$

Martin R already made get_sum_of_factors a lot faster by going only up to sqrt(n). You can do even better by using prime factorization as shown below. This also at most goes up to sqrt(n), but reduces n and thus sqrt(n) in the process. Here are times for computing the sums of factors for num from 0 to 1,000,000 with the sqrt-method and with my prime-method (benchmark here):

round 1
get_sum_of_factors1 11.436 seconds
get_sum_of_factors2 1.767 seconds

round 2
get_sum_of_factors1 11.397 seconds
get_sum_of_factors2 1.675 seconds

round 3
get_sum_of_factors1 10.539 seconds
get_sum_of_factors2 1.699 seconds

Here's the code:

int get_sum_of_factors(int n) {
    if (n < 2) {
        return 0;
    }
    int sum = 1, n0 = n;
    for (int p = 2; p * p <= n; p += 1 + (p > 2)) {
        int m = 1;
        while (n % p == 0) {
            n /= p;
            m = m * p + 1;
        }
        sum *= m;
    }
    if (n > 1)
        sum *= n + 1;
    return sum - n0;
}

It finds prime factors. Imagine you're at some prime \$p\$ and you already have the (sum of) divisors made up from primes smaller than \$p\$. How do we incorporate \$p\$? Let's say the remaining value \$n\$ is divisible by \$p\$ thrice (i.e., by \$p^3\$ but not by \$p^4\$). Then you can build additional new divisors by multiplying previous divisors by \$p\$, \$p^2\$ or \$p^3\$. Any divisor multiplied by \$p\$, \$p^2\$ or \$p^3\$ becomes \$p\$, \$p^2\$ or \$p^3\$ times as large (duh :-). Thus the sum of all divisors gets multiplied by \$m = 1+p+p^2+p^3\$ (the \$1\$ is for the previously found divisors).

How to compute \$m = 1+p+p^2+p^3\$? Easy. For example to go from \$1+p+p^2\$ to \$1+p+p^2+p^3\$ you multiply by \$p\$ to get \$p+p^2+p^3\$ and then add the \$1\$.

As the method finds the sum of all divisors, including the original n, we store it in a variable and subtract that in the end.

Two more reviewy things:

  • You say you find the "first 10 amicable numbers". They do happen to be among your output, but it's not really what you're doing. What you're really doing is find the first 10 amicable pairs, where pairs are ranked by the larger number in the pair. You're btw also not showing the first 20 amicable numbers that way, as you're missing 63020, which is smaller than both numbers in your last pair (it's partner is 76084, which is larger than both).

  • Your loop condition is i < num/2+1. It would be simpler and meaningful to do i <= num/2.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

After implementing both of the suggestions given by Miguel Avila and Martin R, the time taken to calculate was significantly faster.

Original code

#include<iostream>

int GetSumOfFactors(int num){
    int sum = 0;
    for(int i = 1;i < num/2+1;i++){
        if(num % i==0){
            sum+=i;
        }
    }
    return sum;
}
int main(){
    int sum_of_factors = 0;
    int counter = 0;
    int num = 0;
    for(;;){
        num++;
        sum_of_factors = GetSumOfFactors(num);
        if(num == sum_of_factors) continue;
        if (GetSumOfFactors(sum_of_factors) == num && num > sum_of_factors){
            std::cout << "Pair: " << num << " " << sum_of_factors << "\n";
            counter+=1;
        }
        if(counter == 10) break;
    }
    return 1;
}

Time taken to calculate amicable numbers:

// Amicable numbers:        10    20    30
// Average Time taken(s)  5.002   32+   --- 

The biggest improvement was made after the suggestion given by Martin R which was changing how the GetSumOfFactors(int num) function worked. Refer to his post to see it.

new function:

int GetSumOfFactors(int num) {
    int sum = 1;
    int squareroot = (int)sqrt(num);
    for(int i = 2;i <= squareroot;i++){
        if(num%i==0){
            sum+=i;
            if(num/i != i)
                sum+=num/i;
        }
    }
    return sum;
}
// Amicable numbers:        10     20    30
// Average Time taken(s)  0.101   0.324  1.201 

After implementing the remaining optimization tactics given by Martin R

// Amicable numbers:        10     20    30
// Average Time taken(s)  0.09   0.24   0.99

After this, I added an optimization of my own, which was that two amicable numbers have the same parity. That is they both can be even and even or odd and odd. But both of them cannot be different.

Note: I also moved finding amicable numbers to another function new function:

void PrintAmicableNumbers(int number_of_amicable){
    int sum_of_factors = 0;
    int num = 0;
    for(int i = 0;i < number_of_amicable;num++){
        sum_of_factors = GetSumOfFactors(num);
        if(num == sum_of_factors || num%2 != sum_of_factors%2) continue;
        if (num > sum_of_factors && GetSumOfFactors(sum_of_factors) == num){
            std::cout << "Pair: " << num << " " << sum_of_factors << "\n";
            i++;
        }
    }
}
// Amicable numbers:        10     20    30
// Average Time taken(s)  0.07   0.23   0.95

Lastly I changed the line std::cout << "Pair: " << num << " " << sum_of_factors << "\n"; to printf("Pair: %d %d\n",num,sum_of_factors);

This is what my final code looked after posting my question on code review

#include<math.h>
#include<iostream>

int get_sum_of_factors(int num) {
    int sum = 1;
    int squareroot = (int)sqrt(num);
    for(int i = 2; i <= squareroot; i++) {
        if(num%i==0) {
            sum+=i;
            if(num/i != i)
                sum+=num/i;
        }
    }
    return sum;
}

void PrintAmicableNumbers(int number_of_amicable) {
    int sum_of_factors = 0;
    int num = 0;
    for(int i = 0; i < number_of_amicable; num++) {
        sum_of_factors = get_sum_of_factors(num);
        if(num == sum_of_factors || num%2 != sum_of_factors%2) continue;
        if (num > sum_of_factors && get_sum_of_factors(sum_of_factors) == num) {
            printf("Pair: %d %d\n",num,sum_of_factors);
            i++;
        }
    }
}
int main() {
    PrintAmicableNumbers(10);
    return 0x1;
}

The new code was 97.146% reduction in time , the results speak for themselves. Thanks, Martin R and Miguel Avila!

Note: Reduction in time calculated by using: ((old time - new time) / old time) * 100

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ What exactly does the "197.146%" compare? \$\endgroup\$ – superb rain Sep 6 at 11:57
  • \$\begingroup\$ And what were those times? I don't see any that would give me 197.146%. \$\endgroup\$ – superb rain Sep 6 at 12:04
  • \$\begingroup\$ I don't see 97%, either. Why do you refuse to name the times? \$\endgroup\$ – superb rain Sep 6 at 12:14
  • \$\begingroup\$ I don't, I thought you would see it. 24 seconds for 10 amicable numbers earlier on my machine and then the new code took 0.09 seconds. is there something wrong? \$\endgroup\$ – Aryan Parekh Sep 6 at 12:16
  • \$\begingroup\$ And how do you get from those times to 97%? \$\endgroup\$ – superb rain Sep 6 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.