current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite

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.

My question is about the efficiency of my code, 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.

Here is my code: 

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

share|improve this question
    
I can verify that this code does indeed seem to work, but indeed it is slow. And honestly, slowness is not its only problem. –  Simon André Forsberg yesterday
    
@SimonAndréForsberg maybe you could provide a solution to the problem/s, that would be most helpful to me. –  Daedric yesterday
1  
Did you have a look at the existing questions about PE #12? Most of the suggested performance improvements are language-independent. Here is one in Java: codereview.stackexchange.com/questions/74895/… –  Martin R yesterday
2  
As you get further into the project euler problems, you'll begin to realise that they will very often require you to do some mathematical analysis further to get the problem into a form you can attack programmatically. The naive algorithm will usually take an unfeasibly large amount of time (or space!) –  Ben Aaronson yesterday
    
Thank you all for your help in this matter, especially @SimonAndréForsberg. I realize now this maybe a bit out of my league, but hopefully I can come back to it after I have learned at bit more on the subject. My java understanding must also be improved, I started using Java 3 or 4 days ago. –  Daedric 23 hours ago

2 Answers 2

up vote 3 down vote accepted

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)

share|improve this answer
up vote 0 down vote

First of all, your real task is to calculate number of factors. Not factors themself.
Let's start with defining formula for your factors. You could divide set of factors for each number to ones those are prime factors and others those are their derivatives. Then, let's suppose you have number N.

// Here, primeFactors would be a collection of factors x1, x2, ..., xk
// where xk would be the largest prime factor of N
// and x1 is the smallest (2).
// To implement getPrimeFactors you could calculate sieve of Eratosphen large enough and take slice from 0 to index of xk.
// Index of xk probably could be easily found if you'll make binary search for N in sieve
// and then backtrack to first divisor occurence
int[] primeFactors = getPrimeFactors(N);
// Now you should generate maximum power for each.
// (English is not my native, so I could probably make errors in terms)
// Under maximum power I mean maximum k in b^k (where, b is factor) such that b^k is less than N.
// Naive algorithm will work in O(n*log(n)) where n is length of slice you took from Eratosphen's sieve.
int[] primeMaxPowers = calculateMaxExponents(primeFactors);
// Now you could generate your factors.
// That would be all possible combinations of products of primeFactors each of them in some power (from 0 to its corresponding max power).
// But wait, you don't need it. You need only number of combinations.
int numberOfDivisors = 1;
for (int i : primeMaxPowers) {
    numberOfDivisors = numberOfDivisors * (i + 1); // I add 1 to i, because zero is also possible variant of power of prime factor 
}

I think it's a possible replacement for your:

while (a <= z){
    if ((z % a) == 0) {
        t += (String.valueOf(a) + "|");
        f++;
    }
    a++;
}
share|improve this answer

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.