Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28 We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Here is my code :

package coderbyte;

public class Java {

    public static void main(String[] args) {

        long start = System.nanoTime();

        int number = 0;
        int index = 0;
        boolean found = false;

        while (!found) {
            int counter = 0;
            index++;
            number = index * (index + 1) / 2;
            for (int i = 1; i * i <= number; i++) {

                if (number % i == 0) {
                    counter = (number % i == i ? counter + 1 : counter + 2);
                    if (counter > 500) {
                        found = true;
                        break;
                    }
                }

            }

        }

        System.out.println(number);

        System.out.println(System.nanoTime() - start);
    }
}

Any tips on how to improve the runtime and possible shorten the code.

share|improve this question
    
For Euler problems a little math always help out. You can easily find that n % i == i will only occur for index=1 - so it's not necessary to consider. – bdecaf Sep 16 '15 at 14:52
1  
Surely a typo. It must be n / i == i. – vnp Sep 16 '15 at 19:10
    
yes... it was a typo..... my bad... – Altamash Khan Sep 16 '15 at 19:11
up vote 3 down vote accepted

Your solution is not good as you use a single method, stuffing everything inside, with no order nor logic.

It must be rebuilt from scratch.


public class TriagularNumberWithManyDivisors {

Use long, descriptive names, Example is not acceptable by any standard.

static final int DIVISORS_WANTED = 500;

I may have fun running this code for any number of divisors and I really do not want to go haunting for a magic number to change inside the code.

public static int triangular(int n) {
    return n * (n + 1) / 2;
}

This is a function, a part of your program that does only one thing, the funciton name also serves as documetation.

public static int divisors(int n) {
    int counter = 0;
    int limit = (int) Math.sqrt(n);
    for (int i = 1; i <= limit; i++) {
        if (n % i == 0) {
            counter += (n % i == i ?  1 : 2);
        }
    }
return counter;
}

The code for counting divisors was kinda mixed in the main loop, and you had to pay the cost for not extracting it to a function in terms of an ugly boolean flag and two nested loops.

    public static void main(String[] args) {

        for (int i = 0; true ; i++) {
            if (divisors(triangular(i)) > DIVISORS_WANTED) {
                System.out.println(triangular(i));
                break;
            }
        }
    }

}

Themain method, it is incredibly trivial to understand what this does now. It calls the others methods in a high level fashion, highlighting the algorithm.

share|improve this answer
    
Thanks for helping me out.... Yes my code was messed up... because I was only trying to focus on the algorithmic part of the code.... and yes having methods really helps a lot.... Thanks for pointing in the correct direction.. – Altamash Khan Sep 16 '15 at 17:34
    
@AltamashKhan Glad I helped :) If I sounded angry in any way, that was not my intention :) – Caridorc Sep 16 '15 at 18:37
1  
Lol no..... mistakes need to be corrected... and programming needs to be loved :D – Altamash Khan Sep 16 '15 at 18:54

Improving runtime

As with any Project Euler problems you have to invest in math. This particular problem requires understanding of the following:

  • number of divisors is multiplicative: \$\sigma(nm) = \sigma(n) \sigma(m)\$ for coprime \$n, m\$.

  • sequential numbers (such as index and index + 1 are coprime

  • Therefore, instead of factoring index * (index + 1)/2 you should factor index and index + 1 independently. Not only each of them is much smaller than the number you are currently factoring, but you may reuse the factorization: index + 1 becomes index of the next iteration. Division by 2 slightly complicates the process.

share|improve this answer
    
hmm... an iterative way seems a really better option.... guess i will have to put my head on this one for some more time.... Thanks a lot.... – Altamash Khan Sep 16 '15 at 19:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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