2
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$
    – bdecaf
    Sep 16, 2015 at 14:52
  • 1
    \$\begingroup\$ Surely a typo. It must be n / i == i. \$\endgroup\$
    – vnp
    Sep 16, 2015 at 19:10
  • \$\begingroup\$ yes... it was a typo..... my bad... \$\endgroup\$ Sep 16, 2015 at 19:11

2 Answers 2

3
\$\begingroup\$

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 function name also serves as documentation.

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;
        }
    }
}

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

\$\endgroup\$
3
  • \$\begingroup\$ 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.. \$\endgroup\$ Sep 16, 2015 at 17:34
  • \$\begingroup\$ @AltamashKhan Glad I helped :) If I sounded angry in any way, that was not my intention :) \$\endgroup\$
    – Caridorc
    Sep 16, 2015 at 18:37
  • 1
    \$\begingroup\$ Lol no..... mistakes need to be corrected... and programming needs to be loved :D \$\endgroup\$ Sep 16, 2015 at 18:54
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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.... \$\endgroup\$ Sep 16, 2015 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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