Most Efficient way to Compute the sum of divisors of N (1 ≤ N ≤ 1 000 000 000)

Question

I want to write a code which computes the sum of divisors of a number N(1 ≤ N ≤ 1 000 000 000), excluding the number itself.

However, I need an efficient way to do it. It suppose to print the answer under 1 second. I know it depends on hardware etc. But I have an i7 machine though it takes more than a second (for the worst case scenario which is 1000000000 ) because of my poor code.

So to make it more understandable:

EX: Sample input: 10 --> Output should be: 8 (because we know 1 + 2 + 5 = 8)

EX: Input: 20 --> Output suppose to be: 22 ( 1 + 2 + 4 + 5 + 10 = 22 )

So far i wrote this:

public class Main
{
public static void main(String[] args)
{
    @SuppressWarnings("resource")
    Scanner read = new Scanner(System.in);

    System.out.print("How many times you would like to try: ");
    int len = read.nextInt();

    for(int w = 0; w < len; w++)
    {
        System.out.print("Number: ");
        int input = read.nextInt();

        int remains = 1;
        int sum = remains;

        /* All I know we only need to check half of the given number as 
           I learned ages ago. I mean (input / 2) :D */

        for(int i = 2; i <= input / 2; i++)
        {
            if(input % i == 0) sum += i;
        }

        System.out.print("Result: " + sum);
    }

}
}

So the question is How to improve this solution ? How to make it more efficient or let me put it this way. Is there a way to do it more efficient ?

Answer 1

Here is a simple improvement which will most probably meet your time constraints. For every divisor i of N, there is also a corresponding divisisor N/i. Thus to find all pairs of divisors, you need only to loop from 1 to the square root N. So try something along the lines of

    int maxD = (int)Math.sqrt(input);
    int sum=1;
    for(int i = 2; i <= maxD; i++)
    {
        if(input % i == 0)
        {
           sum += i;
           int d = input/i;
           if(d!=i)
              sum+=d;
        }
    }

Note that the "prime factorization" method from the other answer method hides the complexity of the algorithm behind an invisible factorization method. And when you implement a simple form of prime factorization like "trial division", you end up by an algorithm which works very similar like the one above. So the prime factorization method may speed up things up for values of N with many small prime factors, but not when N itself is a prime (at least not, when you don't want to implement a very sophisticated prime factorization method).

Answer 2

A much more efficient way would be to factorize the number into prime factors (using existing libraries, although I do not know one by heart).

Say the factorization is a HashMap<Integer,Integer> factorization where each prime factor is mapped to its multiplicity, then one can compute your sum as follows.

int N = 84684684; //your integer
HashMap<Integer,Integer> primeFactorization = factor(N);
long total = 1;
for (int p:primeFactorization.keySet()) {
    int factor = 1;
    for (int i=0;i<primeFactorization.get(p);i++) {
        factor*=p;
        factor+=1;
    }
    total*=factor;
}
return total-N;

This should be much, much faster, since you compute the result largely as a product. For example, for 10 you have 10=2*5 and hence the result is (1+2)(1+5)-10=8. For 20 the result is (1+2+4)(1+5)-20=22.

For 1 000 000 000 = 2^9 * 5^9, the result should hence be (1+2+4+8+...+512)*(1+5+25+...+5^9)-1 000 000 000 = 1497558338. I did this computation by hand, rather than requiring 1 second on an i7 processor.

Answer 3

You seem to be starting with code. That's completely wrong. You are solving a mathematical problem, so you need to solve the mathematics first.

Take the number 7 x 127 = 889. 7 and 127 are prime numbers. Can you think of a way to find all the divisors of 889, when I gave you the two prime factors? The answer: You get all divisors of 889 by taking one of the numbers (1, 7) and multiplying by one of the numbers (1, 127). That's four different products, including 7 x 127 = 889 which you didn't count. What's the sum of all the divisors, without finding all the divisors? Since you combined each number of (1, 7) with each number of (1, 127), the sum of all the divisors is (1 + 7) x (1 + 127) = 8 x 128 = 1024, including the 889 which you didn't count.

If you took the number 16 x 31 = 496, the possible products would be created by multiplying one of the numbers (1, 2, 4, 8, 16) by one of the numbers (1, 31), and the sum of all products is (1 + 2 + 4 + 8 + 16) x (1 + 31).

So to figure out the number of divisors of a number, you factor it into a product of distinct primes, then you figure out how to translate the maths above into code.

Answer 4

Here is one of the efficient algorithm for counting number of divisors and also summing them up for giving the correct output.

import java.math.BigInteger;
import java.util.Scanner;

class ProductDivisors {

public static BigInteger modulo=new BigInteger("1000000007");
public static BigInteger solve=new BigInteger("1");
public static BigInteger two=new BigInteger("2");
public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner sc=new Scanner(System.in);
    int N=sc.nextInt();
    BigInteger prod=new BigInteger("1");
    while(N-->0){
        prod=sc.nextBigInteger();
        solve=solve.multiply(prod);
    }
    BigInteger x = new BigInteger("2");
    BigInteger total = new BigInteger("0");
    BigInteger totalFactors =new BigInteger("1");
    BigInteger sum=new BigInteger("0");
    while (x.multiply(x).compareTo(solve) <= 0) {
        int power = 0;
        while (solve.mod(x).equals(BigInteger.ZERO)) {
            power++;
            sum=sum.add(x);
            solve = solve.divide(x);
        }
        total = new BigInteger(""+(power + 1));
        totalFactors=totalFactors.multiply(total);
        x = x.add(BigInteger.ONE);
    }
    if (!(solve.equals(BigInteger.ONE))) {
        totalFactors =totalFactors.multiply(two);
    }
    System.out.println(sum);
}

}

In above code counting of divisor is also done so we can get the number of divisors of the number. Any suggestion if there is.