Project Euler #3

In JavaScript:

//this script takes a long time to run for the real number, and
//you may need to make the browser continue the script several times,
//modified number to make it quicker... change back to see in action
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37], factors = [], number = 456;
//real num = 600851475143;
//take the first prime number 2, and divide the number by it
//if it is modulus 0, then use it
//if the current value is higher than the largest prime we currently have,
//then find next prime and go again
while (number !== 1){
  var isPrime = findByPrimes();
  if (isPrime === false)
    findNextPrime();
}

function findByPrimes(){
  var isPrime = false;
  for (var i = 0; i < primes.length; i++){
    isPrime = determinePrimeFactor(i);
    if (isPrime)
      break;
  }
  return isPrime;
}

function determinePrimeFactor(i){
  if (number % primes[i] === 0){
    factors[factors.length] = primes[i];
    number = number / primes[i];
    return true;
  }
  return false;
}

function findNextPrime(){
  var highest = primes[primes.length-1];
  highest += 1;
  for (x in primes){
    if (highest % x === 0)
      break;
    else
      primes[primes.length] = highest;
  }
}

for (var i = 0; i < factors.length; i++){
  if (factors[i]) document.write(factors[i], "<br />");
}
document.write("largest prime factor: ", factors[factors.length-1], "<br />");

on GitHub

Email address

Sign Up