3

I have been working on the Project Euler questions, and in solving question 3 I came across something odd.

Question 3 asks you to "Find the largest prime factor of the number 600851475143"

I solved it as so:

var search = 600851475143;
var highest = 0;
var primes = [2,3,5,7,11];

function isPrime(num) {
    for (var i = 0; i < primes.length; i++) {
        if (num === primes[i]) {
            return true;
        }
        else if (num % primes[i] === 0) {
            return false;
        }
    }
    primes.push(num);
    return true;
}


for (var n = 2; n <= Math.floor(Math.sqrt(search)); n++) {
    if (isPrime(n) && search % n === 0) {
        highest = n;
    }
}

console.log(highest);

This took 7534.188ms this was actually my second version of the program.

In the first version the only difference was that in the for loop in the isPrime function stated 

i <= primes.length

When this change was in place the program took 72084.540ms

That is a rise from around 8 seconds to around 72 second, that is 9 times slower.

I do not believe that the extra iteration would account for such an increase in time. My initial thought was that as it was looking for an index that does not exist, but surely this would crash the program and not just cause it to run slower.

Does anyone have any insight into this?

Anthony O'Brien
  • 115
  • 7
  • because the value of search is a large number. Your loop uses the value of search as the continuation. How many times do you think you increment n before it is equal to the sqrt of search? – bhspencer Feb 19 '16 at 00:38
  • 1
    _"Question 3 asks you to "Find the largest prime factor of the number 600851475143""_ Have you tried iterating beginning at the number itself ? – guest271314 Feb 19 '16 at 00:41
  • I can not figure out a way to iterate from the number itself as the isPrime function requires all previous primes to find the next. It is an application of the Sieve of Eratosthenes. – Anthony O'Brien Feb 19 '16 at 00:58
  • Possible duplicate of http://stackoverflow.com/questions/8229037/prime-factor-and-javascript – guest271314 Feb 19 '16 at 03:05

2 Answers2

3

Your outer loop iterates 775146 times. That is the sqrt of 600851475143. Your inner loop iterates at least 5 times and increases. So the total number of iterations is at least 3875730. That takes a while.

Try inserting a count of the number of times your inner loop is entered. That count will be directly proportional to the run time of your code.

bhspencer
  • 13,086
  • 5
  • 35
  • 44
  • 1
    The inner loop increases in iterations every time it finds a prime. So it's not just 5, it just starts at 5. – Erik Feb 19 '16 at 00:42
  • Both versions enter the inner loop 775145 times. I believe the answer by Erik is the most likely here. – Anthony O'Brien Feb 19 '16 at 00:54
1

Your problem is probably caused by the fact that in Javascript, this code:

var primes = [2,3,5,7,11];
console.log(primes[12]);

produces the output undefined, even though primes[12] is way out of bounds of the array.

Javascript is not like other languages in this respect - going out of bounds of an array does not cause a crash but instead returns an undefined value and allows the program to merrily continue on. undefined is an actual value that can be stored in a variable, so it will continue to evaluate the if statements and exit the loop after the last iteration.

Comparisons against undefined are slow, at least in Chrome. See this Stackoverflow question for some performance information.

Community
  • 1
  • 1
Erik
  • 5,355
  • 25
  • 39
  • Would that not just crash the program rather than cause it to run slowly? – Anthony O'Brien Feb 19 '16 at 00:54
  • No, Javascript is not like other languages in this respect - going out of bounds of an array does not cause a crash but instead returns an `undefined` value and allows the program to merrily continue on. `undefined` is an actual value that can be stored in a variable, so it will continue to evaluate the if statements and exit the loop after the last iteration. – Erik Feb 19 '16 at 05:52