A faster way to compute the largest prime factor I am self-learning js and came across this problem(#3) from the Euler Project


  The prime factors of 13195 are 5, 7, 13 and 29.
  
  What is the largest prime factor of the number 600851475143 ?


Logic:


Have an array primes to store all the prime numbers less than number
Loop through the odd numbers only below number to check for primes using i
Check if i is divisible by any of the elements already in primes.


If yes, isPrime = false and break the for loop for j by j=primesLength
If not, isPrime = true

If isPrime == true then add i to the array primes and check if number%i == 0


If number%i == 0% update the value of factor as factor = i

Return factor after looping through all the numbers below number


My code:



function problem3(number){
 let factor = 1;
 let primes = [2]; //array to store prime numbers

 for(let i=3; i&lt;number; i=i+2){  //Increment i by 2 to loop through only odd numbers
  let isPrime = true;
  let primesLength= primes.length;

  for(let j=0; j&lt; primesLength; j++){
   if(i%primes[j]==0){
    isPrime = false;
    j=primesLength; //to break the for loop
   }
  }

  if(isPrime == true){
   primes.push(i);
   if(number%i == 0){
    factor = i;
   }
  }
 }
 return  factor;
}

console.log(problem3(600851475143));




It is working perfectly for small numbers, but is quite very slow for 600851475143. What should I change in this code to make the computation faster?

Edit: Updated code based on feedback
There are many questions about Project Euler 3 on this site already.  The trick is to pick an algorithm that…


Reduces n whenever you find a factor, so that you don't need to consider factors anywhere near as large as 600851475143
Only finds prime factors, and never composite factors, so that you never need to explicitly test for primality.


Your algorithm suffers on both criteria: the outer for loop goes all the way up to 600851475143 (which is ridiculous, because even if you optimistically assume that it takes one nanosecond per loop, that would be 5 minutes), and you're testing each of those numbers for primality (which is incredibly computationally expensive).