CODEWITHSUNDEEP
java
user2396041
user2396041

Reputation: 31

Project Euler 12: Triangle Number with 500 Divisors

I was reading through the solution to Project Euler Problem 12 on MathBlog and I have some trouble understanding the logic behind the codes. The program uses prime factorisation to find the number of divisors of a triangle number.

private int PrimeFactorisationNoD(int number, int[] primelist) {
    int nod = 1;
    int exponent;
    int remain = number;

    for (int i = 0; i < primelist.Length; i++) {
        // In case there is a remainder this is a prime factor as well
        // The exponent of that factor is 1
        if (**primelist[i] * primelist[i] > number**) {
            return nod * 2;
        }

        exponent = 1;
        while (remain % primelist[i] == 0) {
            exponent++;
            remain = remain / primelist[i];
        }
        nod *= exponent;

        //If there is no remainder, return the count
        if (remain == 1) {
            return nod;
        }
    }
    return nod;
}

I understand most part of the program except for the highlighted portion "primelist[i] * primelist[i] > number". I have trouble understanding the necessity of the this line of code. I will use an example to illustrate my point. Let say I have a number 510 = 2*3*5*17. The highlighted code will only be true when Primelist goes to number 23. But by the time the list goes to number 17, the condition remain == 1 will be true and program would have exited the loop. Would it be better if I change the code to if(remain==primelist[i]) since the loop would end when primelist goes to number 17 instead of 21?

Upvotes: 1

Views: 452

Answers (2)

starblue
starblue

Reputation: 56802

First, it should better use remain:

primelist[i] * primelist[i] > remain

It is an optimization, as there can be no divisors between the square root of remain and remain, so you only have the factor remain left.

Also, the variable name exponent is lying, it really contains the exponent plus one. Better initialize it to zero and multiply by exponent + 1.

Upvotes: 0

Alex Becker
Alex Becker

Reputation: 433

The if condition speeds up the code in certain situations (although it should have "remain" in place of "number"). Once primelist[i] is reached we know that remain is not divisible by primelist[0] through primelist[i-1]. If primelist[i]^2>remain then we can conclude that remain is some prime between primelist[i] and primelist[i]^2-1 (inclusive), as if remain=ab then both a,b would have to be at least primelist[i] so remain would be at least primelist[i]^2, a contradiction. Thus we can stop searching for primes dividing remain.

For an example where this is faster, take number=7. Then the condition is triggered when we reach 3 (as 3^2=9>7), so we do not need to check all the primes up to 7.

Upvotes: 2

Related Questions