Highly divisible triangular number

Question

Highly divisible triangular number, my solution

My solution of challenge from Project Euler takes too much time to execute. Although on lower numbers it works fine. Anyone could look up to my code and give me any advice to improve it? The content of the task is:

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?

 `public static void main(String[] args) {
        int sum = 0;
        int count = 0;
        for (int i = 1; i <= Integer.MAX_VALUE; i++) {
            sum += i;
            for (int j = 1; j <= sum; j++) {
                if (sum % j == 0) {
                    count++;
                }
            }
            if (count > 500) {
                System.out.println(sum);
                break;
            } else {
                count = 0;
            }
        }

    }`

Answer 1

Consider any set of primes (p₁, p₂, p₃. . . p_n) that factor a given number. Then the total number of divisors of that number are the products of (e₁ + 1, e₂ + 1, e₃ + 1 ... e_n+1) where e is the exponent of the corresponding prime factor (i.e. the number of times that prime divides some number N).

There are three pieces to this answer.

• The main driver code
• the method to find the prime divisors.
• and a Primes class that generates successive primes using an iterator.

The Driver

• first instantiate the Primes class and initialize the triangleNo
• Then continually generate the next triangular number until the returned divisor count meets the requirements.

Primes primes = new Primes();
long triangleNo = 0;
for (long i = 1;; i++) {
    triangleNo += i;
    
    int divisors = getDivisorCount(triangleNo, primes);
    if (divisors > 500) {
        System.out.println("No = " + triangleNo);
        System.out.println("Divisors = " + divisors);
        System.out.println("Nth Triangle = " + i);
        break;
    }
}

prints

No = 76576500
Divisors = 576
Nth Triangle = 12375       NOTE: this is the value n in n(n+1)/2.

Finding the prime factors

• takes a value to factor and an instance of the Primes class
• continues to test each prime for division, counting the number of times the remainder is 0.
• a running product totalDivisors is computed.
• the loop continues until t is reduced to 1 or the current prime exceeds the square root of the original value.

public static int getDivisorCount(long t, Primes primes) {
    primes.reset();
    Iterator<Integer> iter = primes;
    int totalDivisors = 1;
    long sqrtT = (long)Math.sqrt(t);
    while (t > 1 && iter.hasNext()) {
        int count = 0;
        int prime = iter.next();
        while (t % prime == 0) {
            count++;
            t /= prime;
        }
        
        totalDivisors *= (count + 1);
        if (prime > sqrtT) {
            break;
        }
    }
    return totalDivisors;
}

The Primes class

• A class to generate primes with a resettable iterator (to preserve computed primes from previous runs the index of an internal list is set to 0.)
• an iterator was chosen to avoid generating primes which may not be required to obtain the desired result.
• A value to limit the largest prime may be specified or it may run to the default.
• Each value is tested by dividing by the previously computed primes.
• And either added to the current list or ignored as appropriate.
• if more primes are needed, hashNext invoked a generating to increase the number and returns true or false based on the limit.

class Primes implements Iterator<Integer> {
    private int lastPrime = 5;
    private List<Integer> primes =
            new ArrayList<>(List.of(2, 3, 5));
    private int index = 0;
    private int max = Integer.MAX_VALUE;
    
    public Primes() {
    }
    
    public Primes(int max) {
        this.max = max;
    }
    
    @Override
    public boolean hasNext() {
        if (index >= primes.size()) {
            generate(15); // add some more
        }
        return primes.get(index) < max;
    }
    
    @Override
    public Integer next() {
        return primes.get(index++);
    }
    
    private void generate(int n) {
        outer: for (int candidate = lastPrime + 2;;
                candidate += 2) {
            for (int p : primes) {
                if (p < Math.sqrt(candidate)) {
                    if (candidate % p == 0) {
                        continue outer;
                    }
                }
            }
            
            primes.add(candidate);
            lastPrime = candidate;
            if (n-- == 0) {
                return;
            }
        }
    }
    
    public void reset() {
        index = 0;
    }
}

Note: It is very likely that this answer can be improved, by employing numerical shortcuts using concepts in the area of number theory or perhaps even basic algebra.