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

• Arthur: "//to break the for loop" Doesn't Javascript have a break?
• Eagle: @Arthur yeah. I'm new to this, and forgot what exactly the word was. It was later pointed out in an answer (now deleted) here, after which I have updated my code. Thanks for pointing out though.
• Arthur: No worries. Knowing that any scope runs until the end is a known aesthetic goal when coding, and people who try to achieve that would probably also do something exactly like that. So I don't think it's that bad, really. And it's not like a single assignment rather than a break would tax the processor much, and a clever compiler might even optimise it away.
• vitaly-t: Here's the fastest solution for JavaScript. It will solve this for 600851475143 in just 0.00001s.
• Thorbjørn Ravn Andersen: When doing tasks like this, it may be helpful to know what the correct result will be. wolframalpha.com/input/…

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

• JollyJoker: The "pick an algorithm" link never explains this explicitly; when you start from low numbers you don't need to check the divisors for primality since the divisors of any composite number would already have been divided out. Even if the original number was divisible by 15, it would already have been divided by 3 and 5.
• 200_success: @JollyJoker I kind of mentioned it, without giving away the spoiler: "Bonus question: in the example above, do we still need to test 19 for primality? Why or why not?"
• JollyJoker: Now I feel like writing a code golfed recursive version, but don't have time...
• JollyJoker: You also test every odd number without explanation, while a naive implementation would test the divisors for primality first. Well, some prefer complete answers, some want the asker to think.
• Peter Cordes: Integer division is still very slow compared to other operations, like multiplication. And even on modern x86 CPUs, isn't fully pipelined. (A new division can't start every clock cycle. Like 1 per 6 cycles on Skylake for 32-bit division, or 1 per 21 to 83 cycles for 64-bit division: agner.org/optimize). 1ns is only 4 clocks on a 4GHz CPU. But if we're being very optimistic, divsd (scalar double floating point) has 1 per 4-clock throughput on Skylake, so maybe we could come close if we come up with a way to check if the result of that is an exact integer in only a couple uops.

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.

1⁄3 of all numbers are divisible by 3, 1⁄5 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 ...

• 1201ProgramAlarm: That sort of stepping can get complicated quickly.
• Solomon Ucko: @1201ProgramAlarm The best way would probably be to keep track of the previous primes and for each new prime, make sure it isn't a multiple of any previous prime. This is useful for generating the infinite sequence of primes (I think of it as an infinite sieve of Eratosthenes), but unless the number is big enough that taking it modulus a small number is too slow, it's best just to find the one modulus instead of finding many smaller ones.
• Graipher: @1201ProgramAlarm It is, however, how a basic sieve works. You assume all numbers are prime (an array of true) and mark of all multiples of two as composite, then all multiples of three, then all multiples of the next number that is still true.

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