2
\$\begingroup\$

I'm working on projecteuler.net problems, and I made this for problem #3:

array = []; // use this to save the prime factors
function factor(number, start){ //begin of the function
  prime=true;
  for(i = start; i < number+1; i++){ //begin of the first loop
    if(number % i == 0){ //is it a divisor of the number?
       for (x = 2; x <= Math.sqrt(i); x++) { //begin of the second lopp
          if (i % x == 0) {prime = false} //is it a prime number?
        }//end of the second loop
       if(prime){ array.push(i); factor(number/i, i); } //if it is a prime number save it and let's do the proccess again. 
    }
  }  //end of the first loop
} //end of the function
array; //So you can see the result

My problem is: I can get the prime factors of all the numbers i pass including the one they put on the example(13195), but when i try to get the prime factors of the one in the exercise(600851475143), my code do save the prime factor in the array but then i get the alert of "script not responding" in mozzila and chromes just stay there doing nothing, any way to solve this?.

Ps: i already solved the exercise but im not satisfied and can't fix it by my own.

\$\endgroup\$
  • \$\begingroup\$ The code works problem is it take too long to execute this number "600851475143" \$\endgroup\$ – José Valdez Ogando Jul 10 '15 at 16:56
  • \$\begingroup\$ Have you tried using a more efficient way to find prime numbers, like the Sieve of Eratosthenes? \$\endgroup\$ – Schism Jul 10 '15 at 17:03
  • \$\begingroup\$ @Schism No i haven't, looking for it now, thanks \$\endgroup\$ – José Valdez Ogando Jul 10 '15 at 17:08
3
\$\begingroup\$

You have excessive, unnecessary comments. You wrote your code clean enough that you don't need them.


for (x = 2; x <= Math.sqrt(i); x++) {
  if (i % x == 0) {prime = false}
}

You are wasting your time here. Once you know the value is not a prime, you do not need to continue looping. This will reduce your time greatly:

for (x = 2; x <= Math.sqrt(i); x++) {
  if (i % x == 0) {
    prime = false;
    break;
  }
}

if(prime){ array.push(i); factor(number/i, i); }

I'm not sure why you continue finding all the small factors when only the largest prime factors are needed. In fact, if you are going to do it manually looping over each number, you should start high and work toward the smaller numbers. A better way to do it, however, would be to use the Sieve of Eratosthenes, as mentioned in the comments on your post.

\$\endgroup\$
2
\$\begingroup\$

I don't disagree with the commenter who suggested using the Sieve of Eratosthenes, but I think that it's worth discussing some aspects of this approach.

  for(i = start; i < number+1; i++){ //begin of the first loop

Rather than calculating number+1 on each iteration of the loop, you can just say

  for(var i = start; i <= number; i++) {

You should also use var to restrict the scope of the variable. As it is, i is probably a global variable, which is probably not what you intended.

       for (x = 2; x <= Math.sqrt(i); x++) { //begin of the second lopp

You don't need to calculate the square root on every iteration.

       var n = Math.sqrt(i);
       for (var x = 2; x <= n; x++) {

Doing it once at the beginning is sufficient.

You don't need a recursive call to factor either. If you instead put the prime checking logic in its own function, you can write this much more simply.

var primes = [];
function isPrime(number) {
  if (primes[number]) {
    return true;
  }

  var maxFactor = Math.sqrt(number);
  for (var i in primes) {
    if (i > maxFactor) {
      break;
    }

    if (number % i == 0) {
      return false;
    }
  }

  primes[number] = true;
  return true;
}

This memoizes the result of the function so that it only needs to process each number the first time that it sees it.

Note that this function assumes that it will be called in sequence starting with 2. You can't start with isPrime(25), as 5 won't be in the array yet. Also, isPrime(1) would return true and break subsequent calls. You can add more code to check that possibility if you want. Or just never call it with a number less than 2.

factors = [];
function factor(number) {
  for (var i = 2; i <= number; i++) {
    if (number % i == 0) {
      if (isPrime(i)) {
        do {
          factors.push(i);
          number /= i;
        } while (number % i == 0);
      }
    }
  }
}

The output for factor(600851475143) is

71, 839, 1471, 6857

which hopefully is correct. I didn't time it, but it seemed to finish in a reasonable time.

\$\endgroup\$

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.