Is there a way for refining this script so that it does not time-out with large values?

Question

I am attamping to solve a Project Euler challenge in which I need to identify the largest prime factor of an input number.

I tried two apporaches:

This approach first determines wheather a value is prime or not. If the value is prime, the if-statement checks if it is a factor. All prime fctors get pushed to the array and thelast value of the array gets returned.

function largestPrimeFactor(number) {

  let arr = [];

  for (let i = 2; i <= number; i++) {

    let flag = 0;

      for (let j = 2; j < i; j++) {

          if (i % j === 0) {
            flag = 1;
            break;
          }
      }

      if (flag === 0) {
        
        if (number % i === 0) {
          arr.push(i);
        }
      }
    }

  return arr[arr.length-1];
}

This approach first determines all the factors of a number. The nested for loop creates and array of remainders for each value. The if statment checks if it is a prime number by determining if all remainders are non-zero numbers.

function largestPrimeFactor(number) {

  let arr = [];

  for (let i = 2; i <= number; i++) {

    if (number % i === 0) {

    let num = i;
    let tempArr = [];

        for (let j = num-1; j > 1; j--) {
          tempArr.push(num %j );
        }

      if (tempArr.every(val => val > 0)) {
        arr.push(num)
      }

    }
  }

  let largestPrime = arr[arr.length-1]
  return largestPrime;
}

Both methods work fine for all test inputs except one which is over 6 000 000 000 (6 billion). The exact input is 600851475143. How can I approach this challenge differently so that the script does not timeout.

Answer 1

If you want to test if a number is prime. You can use Miller-Rabin to solve it in just O(log(n)) which is much faster.

Also, if you want to know the largest prime factor of a number n, you can use a Sieve to find prime numbers and iterate over them, since n could be large, I will use it just to speed it up at a certain point.

using ll = long long;
const int N = 5000000;
int lpf[N];
vector <int> primes;
void sieve(){
    for(int i=2; i<N; i++){
        if(!lpf[i]){
            lpf[i] = i;
            primes.push_back(i);
            for(ll j=1LL*i*i; j<N; j+=i){
                if(lpf[j] == 0) lpf[j] = i;
            }
        }
    }
}

ll largest_prime_factor(ll n){
    ll prime_factor = 1;
    for(int p: primes){
        if(n < N){
            while(n != 1){
                int d = lpf[n];
                prime_factor = max(prime_factor, (ll)d);
                while(n%d == 0) n /= d;
            }
            break;
        }
        if(n%p == 0){
            prime_factor = max(prime_factor, (ll)p);
            while(n%p == 0) n /= p;
        }
    }
    if(n != 1) prime_factor = max(prime_factor, n);
    return prime_factor;
}

It runs in 36ms on my computer for your question, and should also be instantaneous for multiple queries because half of this time is building the sieve, and for numbers less than N it answers in less than log(n). This should work for numbers up to 2.5e13 and with minor modifications could work up to 64-bit numbers in a similar time.