Project Euler 12: maybe solution which uses different math will be useful?

Challenge

Hint page

I will share main differences between my approach and solution from the hint page. If the below is something that could be used on the hints page, let me know, I’ll share the whole solution if needed.

Solution from hints page uses counters to generate triangular numbers:

    i += 1;
    triangleNumber += i;

Alternative approach would be:
use formula to get nth triangular number
Triangular nums on wiki

const getNthTriangular = (n) => {
  return n * (n + 1)/ 2;
}

Solution from hints page uses looping through all potential divisors to get number of divisors and updates counter when new divisor is detected.

Alternative approach would be factorization.

pseudocode:

example: find number of divisors for number 24

step 1

factorize 24 and get number of occurances for each prime factor

24 / 2
12 / 2
6 / 2
3 / 3
1

prime factor 2 has >>> 3 occurances 
prime factor 3 has >>> 1 occurance

step 2

to find number of divisors for 24 >>> use formula below

(a + 1)(b + 1)
where a and b >>> occurances of each prime factor, 
there can be more than 2 prime factors of course


for 24 number of divisors >>> (3 + 1) * (1 + 1) = 4 * 2 = 8

in fact, all divisors of 24:
1 , 2, 3, 4, 6, 8, 12, 24 >>> exactly 8 of them

My implementation of the pseudocode above:

const getNumberofDivisors = (number) => {
  if (number === 1) {return 1;}
  const primeFactorsOccurances = {}
  while (number !== 1) {
    for (let i = 2; i <= number; i++) {
      if (number % i === 0) {
        if (!(primeFactorsOccurances.hasOwnProperty(i))) {
          primeFactorsOccurances[i] = 1;
          number = number / i;
          break;
        }
        else {
          primeFactorsOccurances[i] += 1;
          number = number / i;
          break;
        }
        
      }
    }
  }
  return Object.values(primeFactorsOccurances).map(
    occurance => occurance + 1
    ).reduce(
      (prev, curr) => prev * curr
      ) ;
}
1 Like

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.