Function which finds the sum of factors from one to N

After optimizing my function which I plan to use in
Project Euler 95, I've run into a wall concerning further improvements. This code is destined for my library of project Euler functions, so while readability is nice, it definitely takes a backseat to performance.

I have verified that the output is correct by non-rigorous means (Pasting 10+ non consecutive random numbers for many ranges of output into Wolfram Alpha, no discrepancies), but it remains possible, (but unlikely) that there may be errors. Current run time is between 470-490ms for input size 107. Algorithmic or stylistic review is greatly appreciated.

```
public class sumDivisors2 {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
int[] divisors = divisors((int)Math.pow(10, 7));
}
/**
*
* @param limit
* @returns an array of integers, such that n[i] = the sum of divisors of i + 1
* That is the 0th index is 1, 1st index is 2, etc.
* All divisors of i, including i and 1, are included in the sum.
* (The second index of the array will contain the value three)
*/
public static int[] divisors(int limit){
/**
* The general idea behind the algorithm is to compute the sum of divisors for
* each successive prime, raised to a given power, and multiply them out over the
* entire sieve.
*/
//Setup
long start = System.currentTimeMillis();
int[] primes = generatePrimes(limit);
long pStop = System.currentTimeMillis();
int[] data = new int[limit];
long fStart = System.currentTimeMillis();
fill(data, 1);
long fStop = System.currentTimeMillis();
int index = 0;

//Use bitshifting to quickly multiply out all values of two
int max_pow_two = (int) Math.floor(Math.log(limit) / Math.log(2));
for (int i = 1; i -1; j--) {
int skipCount = 0;
po

Your methods are quite long, which is problematic. They're doing too much, and they're too complicated to follow.

Let's boil divisors down to just the control flow statements...

divisors {
    for {
        for {}
    }

    for {
        if {}
        for {
            if {
                for {
                    if {}
                }
            }
            else {
                for {}
            }
        }
    }

    for {
        for {}
    }
}

This is way too complicated for a single method. We need some refactoring!

The code is confusing. The comments are sparse and it certainly doesn't help that, as an example, this particular method has three different i, three different j, and two k as a result of all the nesting and multiple loops.

We've also cluttered timing code all over the place.

Comments mentioning "quickly" doing things aren't very helpful either. Should we assume the other methods are not "quick" as they don't have comments explicitly mentioning they are quick?

So... let's get some focus on what can be done more specifically...

/**
 * Quickly fill an int array with a given value 
 * @param array the int array   
 * @param value the value
 */
private static void fill(int[] array, int value) {

    int len = array.length;

    if (len > 0) {
        array[0] = value;
    }

    for (int i = 1; i < len; i += i) {
        System.arraycopy(array, 0, array, i, ((len - i) < i) ? (len - i) : i);
    }

}

Given the comment above this method, the actual code in this method isn't even remotely what I'd expect to see. I'd expect this to simply be a wrapper around this:

for (int i = 0; i < array.length; ++i) {
    array[i] = value;
}

If it is anything different than this, then here's what I expect to see...

• Unit tests verifying it produces the same result as the above code.

• Unit tests verifying it is faster than the above code.

• A pile of comments explaining the exact logic of this non-obvious approach (or as a minimum, a link to somewhere explaining why this is faster/better than the straight forward approach).

You public static int[] generatePrimes(int max) seems less than ideal, and I think it's doing more work than necessary...

How about this:

public static int[] generatePrimes(int max) {
    int[] primes = new int[max];
    int primeCount = 0;

    // special cases
    if (max > 2) { primes[primeCount++] = 2; }
    if (max > 3) { primes[primeCount++] = 3; }

    // special cases take care of everything less than 5
    // always increment i by 2 or 4
    // this skips all multiples of 2, 3
    for (int i = 5, w = 2; i < max; i += w, w = 6 - w) {
        boolean isPrime = true;

        // we want to skip the same multiples our outer loop skips
        // if our outerloop skipped the multiples, 
        // there is no use checking if it's divisible by those multiples...
        for (int j = 5, x = 2; j * j < i; j += x, x = 6 -x) {
            if (i % j == 0) {
                isPrime = false;
                break;
            }
        }

        if (isPrime) {
            primes[primeCount++] = i;
        }
    }

    int[] returnArray = new int[primeCount];
    System.arraycopy(primes, 0, returnArray, 0, primeCount); 

    return returnArray;
}

This method eliminates several of your loops. It eliminates several unnecessary checks. And only does what it really needs to do.

And actually, I'm going to argue that the inner loop should be replaced with a simple call to an isPrime method.

public static boolean isPrime(int value) {
    // special cases
    if (value == 2) { return true; }
    if (value == 3) { return true; }
    if (value % 2 == 0) { return false; }
    if (value % 3 == 0) { return false; }

    // special cases takes care of everything less than 5
    // special cases takes care of all multiples of 2 or 3
    // always increment i by 2 or 4 to skip all multiples of 2, 3
    for (int i = 5, w = 2; i * i < value; i += w, w = 6 - w) {
        if (value % i == 0) {
            return false;
        }
    }

    return true;
}

Now our generatePrimes is that much simpler:

public static int[] generatePrimes(int max) {
    int[] primes = new int[max];
    int primeCount = 0;

    // special cases
    if (max > 2) { primes[primeCount++] = 2; }
    if (max > 3) { primes[primeCount++] = 3; }

    // special cases take care of everything less than 5
    // always increment i by 2 or 4
    // this skips all multiples of 2, 3
    for (int i = 5, w = 2; i < max; i += w, w = 6 - w) {
        if (isPrime(i)) {
            primes[primeCount++] = i;
        }
    }

    int[] returnArray = new int[primeCount];
    System.arraycopy(primes, 0, returnArray, 0, primeCount); 

    return returnArray;
}

StackExchange Code Review Q#98737, answer score: 7