6
\$\begingroup\$

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

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.

If the sum of proper divisors of two numbers are equal to each other then they are amicable. For example 284 and 220, whose proper factors sum to 220 and 284 respectively, 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 its 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\$
1

3 Answers 3

4
\$\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
\$\endgroup\$
8
  • \$\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, 2020 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, 2020 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\$
    – user228914
    Sep 6, 2020 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\$
    – user228914
    Sep 6, 2020 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, 2020 at 11:31
4
\$\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 and at the bottom of this answer):

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.

Benchmark code:

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

int get_sum_of_factors1(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;
}

int get_sum_of_factors2(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;
}

std::chrono::steady_clock::time_point begin;
void start() {
    begin = std::chrono::steady_clock::now();    
}
void stop(std::string label) {
    std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
    double seconds = std::chrono::duration_cast<std::chrono::milliseconds> (end - begin).count() / 1000.;
    std::cout << label << ' ' << seconds << " seconds" << std::endl;
}

int main() {
    int max = 1000000;
    for (int round = 1; round <= 3; round++) {
        std::cout << "round " << round << std::endl;
        start();
        for (int i=0; i<=max; i++)
            get_sum_of_factors1(i);
        stop("get_sum_of_factors1");
        start();
        for (int i=0; i<=max; i++)
            get_sum_of_factors2(i);
        stop("get_sum_of_factors2");
        std::cout << std::endl;
    }
    for (int i=0; i<=max; i++) {
        int sum1 = get_sum_of_factors1(i);
        int sum2 = get_sum_of_factors2(i);
        if (sum1 != sum2) {
            std::cout << i << ' ' << sum1 << ' ' << sum2 << std::endl;
        }
    }
}
\$\endgroup\$
3
\$\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)

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.