Java – project Euler problem #12

I have always been happy to challenge with project Euler. I noticed that my solution 12 is my slowest speed, reaching 593.275 milliseconds per run This is the second of my solution, in each crossing ~ 1254.593 milliseconds All my other answers take less than 3 ms to run within 1 ms

My java solution problem 12:

Main ():

int index = 1;
long currTriangleNum = 1;

while (numDivisors(currTriangleNum) <= 500) {
    index++;
    currTriangleNum += index;
}

System.out.println(currTriangleNum);

numDivisors()：

public static int numDivisors(long num) {  
    int numTotal = 0;

    if (num > 1)
        if (num % 2 == 0) {
            for (long i = 1; i * i <= num; i++)
                if (num % i == 0)
                    numTotal+=2;
        } else {
            // halves the time for odd numbers
            for (long i = 1; i * i <= num; i+=2)
                if (num % i == 0)
                    numTotal+=2;
    }
    else if (num == 0)
        return 0;
    else if (num == 1)
        return 1;
    else (num < 0)
        return numDivisors(num *= -1);

    return numTotal;
 }

.

Around the solution forum, some people find that these formulas (n = (P ^ a) (Q ^ b) (R ^ C)... & D (n) = (a 1) (B 1))...) work for them, but I personally don't understand how it will be faster; The hand can also be faster, but not in the program

.

The basic thought process is as follows:

We want to calculate the number of 48 divisors By looking at the following factor tree, we can conclude that 48 = (2 ^ 4) (3 ^ 1) [n = (P ^ a) (Q ^ b) ^ C)...]

48
 /  \
2   24
   /  \
  2   12
     /  \
    2   06
       /  \
      2    3

Knowing this, we construct the formula D (48) = (41) (11) [D (n) = (a 1) (B 1) (C 1)...] to determine that there are 10 factors in 48

d(n)  = (a+1)(b+1)(c+1)...
d(48) = (4+1)(1+1)
d(48) = (5)(2)
d(48) = 10

.

How do I optimize my code? Are these formulas the best solution? I think finding all the main factors and executing the formula will take longer than I already have

Thank you.

Ristian

Edit:

Before anyone started posting links, I had looked at similar problems in so without any luck - I just didn't think their implementation would run faster than I already had

EDIT2：

My second attempt at Eratosthenes screening (for question 10):

int p = 3,n = 2000000;
long total = 0;
boolean[] sieve = new boolean[n];

for (int i = 3; i < n; i += 2)
    sieve[i] = true;

sieve[2] = true;

while (p * p < n) {
    for (int i = p; i < n; i++)
        if (sieve[i] && (i % p) == 0)
            sieve[i] = false;
    p++;

    while (!sieve[p])
        p++;
}

for (int i = 0; i < n; i++)
    if (sieve[i])
        total += i;

System.out.println(total);

Run at ~ 985.399 MS – not much faster than other methods, but not optimized However, it is effective

Solution

Using the basic mathematical structure will greatly change the running time of the program This also applies to question 10. By the way, if you can't do this in a few milliseconds, you use a very inefficient algorithm In fact, I suggest you deal with question 10 first, because question 12 is based on it

I will provide a better algorithm for question 12 below, but first, this is an observation that should significantly speed up your program If two numbers x and y are coprime (i.e. there is no common divisor except 1), then d (x · y) = D (x) · D (y) In particular, for the number of triangles, D (n · (n 1)) = D (n) · D (n 1) Therefore, instead of iterating over the number of triangles n · (n 1), it traverses n: this will greatly reduce the size of the parameters passed to D (n)

If you do this optimization, you will notice that you calculate d (n) twice in a row (once D ((n-1) 1) and once D (n)) This shows that caching d the results is a good idea The following algorithm does this, but it can also be calculated from bottom to top instead of from top to bottom, which is more effective because multiplication is faster than decomposition

Problem 10 can be solved through the simple application of every of erasthenes Fill the Boolean array (i.e. bit vector) with the size of 2000000, so that if I am a prime number, use the sieve [i] = = true; Then summarize and filter the numbers with [i] = = true

Problem 12 can be solved by generalization of Eratosthenes sieve Instead of filtering [i] a Boolean value, indicating whether I am a prime number, making it a number, indicating the number of ways in which it is a non prime number, that is, the number of divisors of I It's easy to do this by modifying Eratosthenes's basic sieve: instead of setting sieve [x * y] to false, add 1

Several subsequent projects benefit from similar approaches to the Euler problem

One problem you may encounter is that in question 12, it is not clear when to stop calculating the sieve You can take two ways: 1 Passing the block calculation sieve as needed is itself a valuable programming exercise (which will require more complex code, the second method) 2 Or start by overestimating a constraint: find a triangular number with more than 500 divisors, and you know you'll stop before or on that number

If you realize that you only need to care about odd numbers, you can get more time, because if n is odd, then d (2 ^ k · n) = (K 1) · D (n), and only find that K and N 2 ^ k · n) are fast on binary computers I will use the details of this optimization as an exercise