3
\$\begingroup\$

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);

})();
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ So the 3rd door, testing the smallest candidate factors, I begin by dividing n (the number we're checking the highest prime factor for) by 'small' prime factors, i.e. 2-3-5-7-11-19- until the prime factor dividing n gives us an int, take that number and repeat until I basically recursively call the highest prime on itself? \$\endgroup\$ – user2879041 Dec 10 '15 at 21:12
  • \$\begingroup\$ Updated.. I think it's all there, but still pretty slow. Been running for about 5 minutes now, even as a node.js file \$\endgroup\$ – user2879041 Dec 11 '15 at 17:07
  • \$\begingroup\$ Disregard, found what I was missing appreciate the help! \$\endgroup\$ – user2879041 Dec 11 '15 at 17:11
0
\$\begingroup\$

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]);

})();
\$\endgroup\$
  • \$\begingroup\$ Give some thought to why you are calling isPrimeFactor(i). \$\endgroup\$ – 200_success Dec 11 '15 at 17:22
  • \$\begingroup\$ @200_success hmm not exactly sure if I understand why I wouldn't call that, is it not necessary? It's necessary (as far as I understand) to make sure the factor of the number isn't just a factor-- but obviously a prime factor \$\endgroup\$ – user2879041 Dec 11 '15 at 17:24
  • \$\begingroup\$ If you have already tried all smaller candidate factors, then …? \$\endgroup\$ – 200_success Dec 11 '15 at 17:26
  • \$\begingroup\$ @200_success oh think I see where you're leading me. so basically, push the smaller factors when a larger one is found into an array (or something) and then check only ones larger than that? is that where you are going with this? \$\endgroup\$ – user2879041 Dec 11 '15 at 17:29
  • \$\begingroup\$ It can be even simpler than that. \$\endgroup\$ – 200_success Dec 11 '15 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.