0

While working on problem 3 of Project Euler, I'm coming across a problem I can't seem to fix where javascript keeps freezing. Here's my code:

var is_prime = function(n) {
  if (n === 1) {
    return true;
  }
  if (n === 2) {
    return true;
  }
  var list1 = []
  for (i = 2; i < n; i++) {
    list1.push(i);
  }
  for (i = 2; i < list1.length; i++) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}

var list_of_primes = function(n) {
  var list1 = [];
  var list2 = [];
  for (i = 2; i < n; i++) {
    list1.push(i);
  }
  for (i = 2; i < list1.length; i++) {
    if (is_prime(i)) {
      list2.push(i);
    }
  }
  return list2;
}
confirm(list_of_primes(1000))

I know my algorithm isn't the most efficient and that I'm just brute forcing the problem, but I'm just wondering what it is I'm doing wrong. I'm pretty sure the problem lies somewhere within this block of code:

  for (i = 2; i < list1.length; i++) {
    if (is_prime(i)) {
    list2.push(i);
    }
  }

I think a potential problem is that my algorithm is taking too long and that is what is causing javascript to freeze. Is there anyway to get my problem to run long enough to give me the answer?

thefourtheye
  • 233,700
  • 52
  • 457
  • 497
Oscar Yih
  • 3
  • 1
  • "I know my algorithm isn't the most efficient..." Could it be that you are just maxing out the CPU while you are brute forcing? Try letting it run overnight and see if you get any results. Or include some console.log() commands in your loop to output the 'current' value of i periodically? – Aren Jan 17 '16 at 07:20
  • I don't think I can be maxing out my CPU. I manage to get this working on python and the answer only took about 1 second. However, when I attempt to translate this code to javascript and run it on jsfiddle or node.js, they both crash within a second. – Oscar Yih Jan 17 '16 at 07:38
  • 1
    @OscarYih Did you try with smaller value like 15? It should work quicker for sure. If it works that means you need to use efficient algorithm instead. Also check the console on browser if you get any errors. – pratikpawar Jan 17 '16 at 07:42
  • Python might be more efficient at this sort of algorithm than Javascript. I've written Javascript that pulls quite a bit of CPU on what seems to be trivial inputs. It might just be a case of hitting the limit of what the language can do. Try monitoring your CPU while you run, if a core is hitting 100%, it's likely you are hitting that wall. Especially if you get the same behavior with node.js (otherwise I'd blame sloppy implementation of the language within the target browser). – Aren Jan 17 '16 at 07:42
  • @pratikwebdev: I tried the code with 15 as the value to test up to, and it caused a lock condition in my browser. Brute force shouldn't have done that with only 15 tests to run. Might be worth tracing through this code line by line to look for infinite loop potential? – Aren Jan 17 '16 at 07:46
  • @OscarYih you could load the script after html elements and see how that goes. It will prevent browser from waiting for script execution. Also if you could remove first for loop in both the functions and use `i – pratikpawar Jan 17 '16 at 08:08
  • @Aren It seems like it could be a logic error, but I've tried going over it in my head for a while now and changing it around and I can't see my error. I'd appreciate it if you could try and find my error. – Oscar Yih Jan 17 '16 at 08:11
  • I don't know why it's freezing (you should add some console logging so you can watch what it does), but regarding your algorithm: what are the two `list1` arrays for? You write to them, but never read from them other than checking the length. I think that makes your algorithm both wrong *and* really inefficient. (`list_of_primes()` will never actually test as high as whatever n is because it will stop at `list1.length` which is always less than n.) – nnnnnn Jan 17 '16 at 08:35
  • 3
    Wait: maybe it's freezing because both your functions use the same global variable `i` as their loop counter? – nnnnnn Jan 17 '16 at 08:42
  • @nnnnnn That seems correct, good catch! [Here's OPs code copy/pasted, with `var i` instead of just `i` so the variable is localized.](https://jsfiddle.net/daCrosby/6nk98zab/) No more timeouts. – DACrosby Jan 17 '16 at 08:51

3 Answers3

1

You could try this. 

var is_prime = function(n) {
 if (n == 1) {
   return true;
  }
 if (n == 2) {
   return true;
  }

  for (var i = 2; i < n; i++) {
    if (n % i == 0) {
      return false;
     }
     }
  return true;
  }

  var list_of_primes = function(n) {
  var list2 = [];

  for (var i = 2; i < n; i++) {
    if (is_prime(i)) {
         list2.push(i);
  }
  }
  return list2;
}
confirm(list_of_primes(1000))

Working fine in less than seconds. https://jsfiddle.net/LL85rxv5/

pratikpawar
  • 2,038
  • 2
  • 16
  • 20
  • Thanks for the solution, I'll be sure to compare your compare your code against mine and see what I did wrong. – Oscar Yih Jan 17 '16 at 08:32
0

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Strictly speaking, 1 is not a prime number so be sure to update that in your code.

Not really sure why your code is timing out, it's just a bit longhand and has an unnecessary array (list1). Anyway, here's a pretty shortened version of the code that comes up with a list of prime numbers from 2 to n. This isn't too efficient for a large number set because it checks every number individually.

var list_of_primes = function(n) {
  var list = [];
  for (i = 2; i < n; i++) {
    if (is_prime(i)) {
      list.push(i);
    }
  }
  return list;
}
function is_prime(i) {
  for (var c = 2; c <= Math.sqrt(i); ++c)
    if (i % c === 0)
      return false;
  return true;
}

If you want a bit more efficiency, look into the Sieve of Eratosthenes which can handle much larger sets:

// Credit: http://stackoverflow.com/a/15471749/1265817
var eratosthenes = function(n) {
  // Eratosthenes algorithm to find all primes under n
  var array = [], upperLimit = Math.sqrt(n), output = [];

  // Make an array from 2 to (n - 1)
  for (var i = 0; i < n; i++) {
    array.push(true);
  }
  // Remove multiples of primes starting from 2, 3, 5,...
  for (var i = 2; i <= upperLimit; i++) {
    if (array[i]) {
      for (var j = i * i; j < n; j += i) {
        array[j] = false;
      }
    }
  }
  // All array[i] set to true are primes
  for (var i = 2; i < n; i++) {
    if(array[i]) {
      output.push(i);
    }
  }
  return output;
};

Working examples: https://jsfiddle.net/daCrosby/wfgq28no/

DACrosby
  • 11,116
  • 3
  • 39
  • 51
0

i is a global variable within is_prime function, which interferes with instance used in list_of_primes function. Fix by declaring i as local like this...

var is_prime = function(n) {
  var i; // <~~ declare i as local variable here
  if (n === 1) {
Billy Moon
  • 57,113
  • 24
  • 136
  • 237