Odd number returning two as prime factor

Question

This function takes a number and returns its prime factors as an array. I ran a bunch of test cases and all comes out correct except this number 90000004000000001.

The code is not optimized at all, so most numbers that large will time out. However, this one test case computes for some reason and it gives me the factors [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5, 5, 89, 241, 1049] which is obviously nonsense since 90000004000000001 is an odd number.

When multiplying the factors together the resulting number is 90000004000000000. 1 lower than the original number.

That's strange, so I tried 90000004000000001 % 2 which returns0.

I'm starting to think my function might not be the problem here but rather modulus or numbers in javascript. How come an even number can be divisible by 2 as in this case?

I put a few test cases as console logs together with the code snippet so you can see the results.

Thanks!

// Assuming it works will factor an integer into its prime components and return them as an array
function factorize(num) {
  num = Math.floor(num);

  // the array to store all factors
  let factors = [];

  // goes through all numbers starting at 2
  // break when a factor is found
  // will also break if num is prime (its own factor)
  let i = 2;
  while (true) {
    if (num % i === 0) {
      factors.push(i);
      break;
    }
    i++
  }

  // i is the factor from the while loop
  // if num is not prime recursively factorize the remainder after factoring out i
  if (i !== num) {
    factors = factors.concat(factorize(num / i));
  }

  return factors;
}


console.log(factorize(16)); //[2, 2, 2, 2]
console.log(factorize(101)); //[101]
console.log(factorize(100001)); //[11, 9091]
console.log(factorize(141)); //[3, 47]
console.log(factorize(90000004000000001)); //[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5, 5, 89, 241, 1049]
console.log(factorize(90000004000000001).reduce((a, b) => a * b)); //90000004000000000

I don't understand the negative sentiment on this site. The question is hardly a duplicate of the question it's supposedly a duplicate of. That question explains the issue, but it wasn't something that was obvious to look for as a new programmer. I provided test cases, code with good comments and clearly stated the issue. Why down vote? — Jensei, Jul 30 '18 at 14:14

Alnitak · Accepted Answer · 2018-07-30T14:16:22.267

Your number is larger than the largest integer that can be exactly stored in a Javascript number value which is Number.MAX_SAFE_INTEGER with a value of 9007199254740991 , i.e. (2 ^ 53) - 1.

Expressed as a power of 2, your number is approximately equal to 2 ^ 56.32077 so it has 3.32 too many "bits" to be expressed accurately, meaning there'll be an error in the region of ±10 for any value in that range.

This is a limitation of the IEEE 754 double precision floating point format.

It is therefore impossible to perform exact integer operations on it.

Just for fun, try this in your JS console:

> console.log(90000004000000001 + 1)
90000004000000000

> console.log(90000004000000001 + 9)
90000004000000020

Odd number returning two as prime factor

1 Answers1