A faster way to compute the largest prime factor

Question

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<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< 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

Answer 1

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).

Answer 2

For starters, you only need to check odd numbers (potential primes) below √X.

If A * B == X, then:

• Either A == B and X is a perfect square, so the largest prime dividing A is the largest prime factor,
• Or one of A and B is less than the other, and thus less than √X.

Without loss of generality, say A is less than B. Then B would be greater than √X, but the largest prime factor in A or B would be the largest prime factor of X.

So, you can start testing B, and just like X, you need to test only numbers less than √B, and when testing A only those less than √A.

You can keep a list of numbers that divide X, I would always try to find a factor of the largest number that divides X:

• If it is prime, it is the largest prime factor.
• But if you do find a factor of the largest, get rid of it and replace it with its two factors. Then once again, find the largest factor and prove it is prime or composite.

I would also start your loop for finding a factor "from the bottom," not from the top, to play the odds.

⅓ of all numbers are divisible by 3, ⅕ divisible by 5, etc. You can divide by 2 as many times as possible before beginning. Then keep track of the largest odd number you have tried (prime or not, that will include all primes), so once they fail, you don't need to try them again.

Answer 3

The first problem is that you are trying to find all prime numbers under number. The number of prime numbers under x is approximately x/ln(x) which is around 22153972243.4 for our specific value of x

This is way too big ! So even if you where capable of obtaining each of these prime numbers in constant time it would take too much time.

This tells us this approach is most likely unfixable.

Answer 4

You already skip all even numbers.
For the same reason, create code that skips:

1. every 3rd #
2. every 5th #
3. every 7th ... 11th ... 13th, maybe ...

Answer 5

This answer is not so much for academic purposes, but rather to show how this can be done real fast, using an existing library. However, the function source code can be easily reused also.

Using prime-lib library (I'm the author):

import {primeFactors} from 'prime-lib';

const allFactors = primeFactors(600851475143); // takes ~0.00001s
//=> [71, 839, 1471, 6857]

const maxPrime = allFactors.reduce((c, i) => Math.max(c, i));
//=> 6857