5

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 ?

migrated from stackoverflow.com Nov 29 '14 at 3:17

This question came from our site for professional and enthusiast programmers.

  • 3
    You haven't indicated how much memory can be used. Eventually, the way fast enough would be to pre-compute all the results, store them in a database, and then do a simple select query when you need an answer. – Arseni Mourzenko Nov 29 '14 at 3:21
  • You need to check up to a square root of N adding two values at a time whenever appropriate. – PM 77-1 Nov 29 '14 at 3:22
  • Thanks for your all responses! MainMa It's a good advice but unfortunately, contract doesn't let use of databases. And PM 77 now I'm working on it! – Jon Snow Nov 29 '14 at 3:41
9

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).

  • 1
    I'm afraid your comparison with the prime factorization method is not correct. Prime testing is pretty fast, so prime numbers will be detected as prime rapidly. Numbers of the form N=p*q with p,q both large prime numbers are the most difficult case, here the factorization will be only slightly faster than what you propose. In any other case it should be much faster. The reason why is that as soon as you have one factor, you can divide it out and you are left with factorizing a smaller number. This is not exploited by your code. – user1111929 Nov 29 '14 at 13:08
  • @user1111929: don't get me wrong, I am not talking about speed (I know you approach is faster). I am talking about the effort of implementing it - for the given time constraints you are just cracking a nut with a sledgehammer. And you did not read my answer thoroughly - I wrote "when implementing prime factorization by trial division". – Doc Brown Nov 29 '14 at 14:20
  • In that case you are correct, I must have missed that part. Indeed, factoring it by trial division faces the same problems, but I'm sure other algorithms should already exist in Java. A quick search ended me up with an implementation of Pollard's rho algorithm, for BigIntegers (so can be speeded up quite a bit for ints) introcs.cs.princeton.edu/java/78crypto/PollardRho.java.html and I'm sure the more advanced algorithms should be already implemented somewhere too. – user1111929 Nov 29 '14 at 14:38
  • Cool! Your Algorithm is far more faster than my first code and thanks a lot for your answer. Of course the first solution is faster after implement it though as you guys discussed above, it takes more effort. – Jon Snow Nov 29 '14 at 18:42
  • I'll mark this answer because if there is someone who digs this question s/he can implement this with just copy and paste. I wish I had enough reputation to vote up both answers. Both answers are very efficient for different cases. Thanks again! – Jon Snow Nov 29 '14 at 18:58
4

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.

  • We are trying to make an Android App which includes this kind of questions and all possible ways of solutions. The point is finding the most efficient way. There are tons of questions like this which we've been working on. However, we need to solve them first :D – Jon Snow Nov 29 '14 at 18:33
  • what would the factor function look like because most of those that i have found look like the other answers solution? – zurbergram Jun 30 '15 at 21:13
  • What do you mean? The function is there and its complexity is vastly lower than the one from the other post. For example, for 100 000 000, the other function would iterate over {2,4,6,8,10,12,14,16,18,20,...,10000} while mine would only iterate 8 times over {2,5}, given that you have (from other code) the prime factorization. – user1111929 Jul 1 '15 at 13:24
  • 1
    @JohnMerih are you familiar with Wolfram Alpha etc. ? – kevin cline Dec 21 '15 at 23:38
2

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.

  • This really helped – not surprising: if one wants to design a fast algorithm, one should probably start at finding a clever mathematical transform. Thanks. – H2CO3 Dec 22 '15 at 18:16
  • Your answer seems pretty much identical to mine, no? – user1111929 Dec 31 '15 at 12:33
  • There's no code in my answer. The code doesn't help learning how to attack the problem. The code doesn't explain why the code would actually give the correct result. The OP didn't want to learn how you write the code, but how to write the code himself. At least that's what I hope. – gnasher729 Apr 14 '16 at 8:09
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.