Effecient Prime Number Sum until Max Number

[devrathnd]

Hi,

I have gone through a lot of pain in optimizing and making this program efficient both with respect to space and time.

1st I implemented Sieve of Eratosthenes instead of conventional trial division method.

Then implemented bit array storage to use less memory.

I wanted to know how can I further improve the performance of this program.

    memset(sp, 0, BITNSLOTS(maxp));
    for(i = 2; i < maxp; i++) {
        if(!BITTEST(sp, i)) {
            sum+=i;
            for(j = i + i; j < maxp; j += i)
                BITSET(sp, j);
        }
    }
    printf("%llu\n",sum);
 

[Banfa]

Line 4: not clear what the purpose of this is

Line 5: You effectively initialise j to i * 2 but you can initialise it to i * i. Any multiple of i less than i must have been covered by a previous iteration.

[devrathnd]

Line 4: It sums all the prime number being generated ie: 'i' will be having the prime number

Line 5: changing to i*i is giving wrong answer.

[Banfa]

Line 5: You also need to change < to <= and you need to test first to make sure that i*i does not overflow the variable, i.e. only perform the loop if i <= maxp/i

[devrathnd]

@Banfa
Any idea on how to decrease the Cyclomatic Complexity of this code ?? The previous code gives Cyclomatic Complexity of 4 while after making changes on your advice its giving Cyclomatic Complexity of 5..

And the speed improved a bit upon the changes but I want to decrease the Cyclomatic Complexity..

[Banfa]

By definition the code I gave increased the cyclomatic complexity of the code. Generally speaking any (or at least many) optimisation would since you are looking for special cases and then doing something different for them (i.e. executing some control statement).

Since cyclomatic complexity basically counts execution paths and what I suggested added an if statement and therefore an additional execution path the cyclomatic complexity went up.

If you want to reduce the cyclomatic complexity then remove the optimisation.