Very slow Project Euler Q3 (largest prime factor of a large number)

Question

My code returns the correct answer for the example (highest prime of 13195 is 29), but when I test against the number in the question my code basically is too slow for my liking.

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

Is there anything obviously wrong with my logic or any ways to improve?

(function(){

var theNumber = 600851475143; // testing this number, sub in 13195 to verify 

var getHighestPrimeFactor = function(number){
    var upto = (number / 2) % 2 == 0 ? (number/2) : Math.floor(number/2);
    var factors = [];

    for(var i = upto; i > 1; i--){
        if(number % i == 0){
            factors.push(i);
            if(isPrimeFactor(i) == true){
                console.log("high prime = " + i);
                return i;
            }
        }
    }
} // end getHighestPrimeFactor

var isPrimeFactor = function(number){
    var upto = number / 2;
    var isItPrime = true;
    for(var i = 2; i < upto; i++){
        if(number % i == 0){
            isItPrime = false;
            break;
        }
    }
    return isItPrime;
} // end isPrimeFactor

var x = getHighestPrimeFactor(theNumber);
console.log(x);

})();

Answer 1

Similar questions have been asked before. You are using the "test the largest candidate factors first" strategy, which does not scale well at all. You should test the smallest candidate factors first.

Answer 2

So the here's the code in JS if anyone wants to see it in action, just required following 200_success's advice and another answer seen here

Project Euler #3 - largest prime factor

That answer led the the improved algorithm below, especially #3 that is listed.

Code here:

(function(){

var n = 600851475143; // testing this number
//var n = 13195; // sub in, largest prime factor is 29
var primeFactors = [];


var findHighestPrime = function(number){
    var bound = Math.floor(number/2); 

    for(var i = 2; i < bound; i+=2 ){
        if(number % i == 0){ // it's a factor, is it prime though? 
            if(isPrimeFactor(i) == true){
                primeFactors.push(i);
                if(number/i == 1){ // stop here, it's the highest prime factor
                    break;
                } else {
                    number = number / i; // "recursively" check the newest number
                }                   
            }
        }
        i = (i%2==0) ? i-= 1 : i; // added this in for speeding up the algorithm a little.
    }
}

var isPrimeFactor = function(number){
    var upto = number / 2; // only need to measure up to half of the number
    var isItPrime = true;
    for(var i = 2; i < upto; i++){
        if(number % i == 0){
            isItPrime = false;
            break;
        }
    }
    return isItPrime;
} // end isPrimeFactor

findHighestPrime(n);
console.log(primeFactors[primeFactors.length-1]);

})();