How to optimize a factor counting algorithm

Question

I've been asked to sum the factors other than 1 and the number itself of every number in an array. The problem is it must be able to handle very large arrays with very large numbers and my current implementation takes very long for arrays of size 100,000,000. My code for counting each numbers factors is

static long countFactors(long num){
    long count=0;
    long max =(long) Math.floor(Math.sqrt(num));
    for(int i=2; i<=max;i++){
        if(num%i==0&&(i*i)!=num){
            // count i and n/i as a factor
            count+=2;
            if(num/i<max){
                max=num/i;
            }
        }            
        else if(num%i==0){
            // just add one factor since it is the numbers root.
            count+=1;

        }
    }

    return count;
}

Does anybody have any optimisation suggestions.

Answer 1

I'm putting the best idea at the beginning of this post:

A number divisible by n is divisible by all the factors of n.

Maybe that is the key to reducing your time complexity. Now the rest:

Right now you perform the test (i*i)!=num O(max) times when it only need be done once. (for(int i=2; i**<**max;i++) then check the square root). You did say very large numbers so this could save a little bit.

Also what is this? if(num/i<max){ max=num/i; } If I am reading correctly, this is superfluous. It never happens that a factor i in this loop is greater than square root of num.

Finally, space permitting, you could make the outside loop over i put the loop through the array on the inside. This would save a tiny bit by not needing to repeat i*i. These are just micro optimizations on your current algorithm.