CODEWITHSUNDEEP
c
poorvank
poorvank

Reputation: 7602

Optimization of my code in c for Project Euler # 23

i am solving Problem no 23 of project euler. I have used a simple logic , i am getting the correct answer but it is taking a great length of time to run the program.

Is there any way i can optimize my code ?.

I am first calculating all the numbers which are a sum of 2 abundant numbers and then subtracting it from the entire sum.

int factorsum(int);
int main()
{
    int i, j, s = 0, t, m;
    for (i = 24; i <= 28123; i++)   //sum of 2abundant nos start from 24
    {
        for (j = 12; j <= i / 2; j++) {
            t = factorsum(j);
            if (t > j) {
                m = i - j;
                t = factorsum(m);
                if (t > m) {
                    s = s + i;
                    break;
                }
            }
        }

    }
    j = 0;
    for (i = 1; i <= 28123; i++)
        j = j + i;
    printf("\n%d", (j - s));
    return 0;
}

int factorsum(int j)        //checking sum of factors
{
    int k, s = 0;
    for (k = 1; k <= (j / 2); k++) {
        if (j % k == 0) {
            s = s + k;
        }
    }
    return s;
}

Upvotes: 1

Views: 482

Answers (1)

Daniel Fischer
Daniel Fischer

Reputation: 183878

The immediate big optimisation is to precalculate the divisor sums. At the moment, you are recalculating factorsum(j) for j = 12, ... for each i. If you calculate the divisor sums once and store them in an array, that becomes a fast (O(1)) lookup instead of an O(j/2) computation.

That alone reduces the running time on my box from three and a half minutes to one second.

The next improvement would be to use a better strategy to compute the divisor sums. Instead of checking each number up to j/2 whether it divides j, you can use the fact that divisors come in pairs, (d, j/d) to only check up to √j (be careful with perfect squares, you must only add the square root once).

That takes it down to 0.05 seconds.

But if you store the sums in an array, you can do even better by reversing the logic, instead of considering one number n at a time and finding its divisors, consider one divisor d and find all its multiples (k*d). That reduces the time needed to calculate the divisor sums from O(limit^1.5) (or O(limit^2) if you divide up to j/2) to O(limit * log limit). (Note: since you are given an absolute limit, the complexity notation isn't strictly applicable here, let's pretend you try to find the numbers that aren't the sum of two abundant numbers up to a variable limit.)

That makes it 0.03 seconds.

Upvotes: 2

Related Questions