Euler Project 12# - highly divisible triangular number

Question

I'm an amateur programmer, new to Java and while attempting the Project Euler Archive 12 (Highly divisible triangular number) I ran into extremely long run time, with no result as of yet.

Is it efficient and what should I do to improve it? Is there a special method to follow when sorting factors of numbers?

Basically I need to find the first triangle number with over 500 divisors.

public class Divisor {

    public static void main(String[] args) {
        int f = 0; //divisors
        int m = 500; //max divisors
        int j = 1; //current number
        int z = 0; //sum (last run achieved: 135878572)
        int a = 1; //current denominator
        String t = ""; //total divisors


            while (f<=m) {
                f = 0;
                z += j;
                j++;
                System.out.println("------");
                System.out.println("t: " + z);
                //Now get factors of each, the first to have over 500 is the answer
                while (a <= z){
                    if ((z % a) == 0) {
                        t += (String.valueOf(a) + "|");
                        f++;
                    }
                    a++;
                }
                System.out.println("f: " + t);
                t="";
                System.out.println("d: " + f);
                a = 1;
            }
            System.out.print("Answer: " + z);
    }

}

Here is an example of my output (first 3 triangle numbers):

------
t: 1   <--- Triangle Number
f: 1|  <--- Factors (Divisors)
d: 1   <--- Total Factors (Total Divisors)
------
t: 3
f: 1|3|
d: 2
------
t: 6
f: 1|2|3|6|
d: 4
------

Also please note: I'm using NetBeans IDE 7.3.1, with Java 1.7

Answer 1

Before we get to the slowness aspect of this code, there are a few other things we should straighten out first:

Variable names

In order to better understand your code, it is helpful to have better variable names.

Whenever you see yourself adding a comment after each variable name to describe it, you are doing something wrong:

int f = 0; //divisors
int m = 500; //max divisors
int j = 1; //current number
int z = 0; //sum (last run achieved: 135878572)
int a = 1; //current denominator
String t = ""; //total divisors

Not to mention that this is just confusing:

System.out.println("t: " + z);
...
System.out.println("f: " + t);
...
System.out.println("d: " + f);
...
System.out.print("Answer: " + z);

I would have expected something like:

System.out.println("t: " + t);
...
System.out.println("f: " + f);
...
System.out.println("d: " + d);

But your output is not very informative at all about what it actually means.

Now, how about we do this?

int divisors = 0;
int maxDivisors = 500;
int currentNumber = 1;
int sum = 0;
int currentDenominator = 1;
String totalDivisors = "";

Now there's no longer a need for the comments describing each variable, and now it will be easier to understand your code.

String concatenation and System.out

A major bottleneck in your code is all the System.out.println messages. You can take the fastest code in the world, and add a bunch of calls to System.out.println to it and it will become a lot slower.

Additionally, actually storing and outputting all the divisors is a major bottleneck. You are storing the divisors by using String concatenation. String concatenation by using the += operator is slow, as a new String object is created every time. It is slightly faster to use the StringBuilder class to perform string concatenation. However, in this case I would recommend getting rid of this output entirely. Once you have checked that the calculation of the number of divisors is correct, you don't need to know what the exact divisors are anymore.

Algorithm

Now to the fun part. Your way of calculating the number of divisors is the good old brute-force-ish way. Loop from 1 to x and see if it is divisible. Makes sense.

But there is a much much much faster way.

Let's take a look at some numbers, shall we?

Number    Divisors
6         4
28        6
36        9
66        8
120       16

Let's take a look at the prime factorization for those numbers

Number    Divisors  Prime Factorization
6         4         2*3
28        6         2*2*7
36        9         2*2*3*3
66        8         2*3*11
120       16        2*2*2*3*5

In how many different ways can we pick the prime factorizations for each of these numbers?

Let's take a look at 36. There are 2x 2's in the prime factorization and 2x 3's. So we can pick 0-2 2's (three combinations) and 0-2 3's (three combinations). 3 combinations * 3 combinations = 9 !!

Coincidence? Let's take a look at 120. There are three 2's, one 3, and one 5. So there's four combinations to pick 2's, two combinations to pick 3's and two combinations to pick 5's. 4*2*2 = 16.

Coincidence? Absolutely not.

Note that we don't actually need to do the actual prime factorization, we just need to know in how many different ways we can pick the prime factors.

Assume that the prime factorization is x*x*x*y*y*z, then there will be 4*3*2 = 24 divisors for that number. No matter what the values of x, y and z are.

This is just a push in the right direction, now I will leave the fun part of implementing the code up to you (or, if you really really just want the codes, which I don't recommend, you can take a look at one of my previous questions in which I have implemented this fast approach)

Answer 2

You could use this piece of fact : 1 to the square root of the number holds exactly half of the divisors , so to get the total number of divisors you just have to multiply by factor '2'. Here is the piece of code: Courtesy : http://cs.miky.ca/java/project_euler/problem_12

#include <stdio.h>
#include <math.h>
long long int genTriangleNum(int n)
{
    int sum = 0;
     int i;
    for(i=1;i<=n;i++)
    {
        sum+=i;
    }
    return sum;
}
int main(int argc, char *argv[]) 
{
     int tester;
     int i;
     int factorCounter=0;
    while(factorCounter<=500)
    {
     factorCounter=0;
     i++;   // counter i for triangular number
     tester = genTriangleNum(i); //ith triangular number
    // 1 to the square root of the number holds exactly half of the divisors
     for(int j = 1;j<=sqrtl(tester);j++) 
     {
      if(tester%j==0)
      {
        factorCounter++;
      } 
     }
     // so multiply it by 2 to include the other corresponding half
     factorCounter*=2;
    }
    printf("%d",tester);
    return 0;
} 

This code took me exactly 1.12 sec on my Mac .