Mryntu

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?

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 insane), and you're testing each of those numbers for primality (which is incredibly computationally expensive).

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.