Mrthfx

"My boss was furious with me and I have been fired" vs. "My boss was furious with me and I was fired"

How to get even lighting when using flash for group photos near wall?

Check if a string is entirely made of the same substring

Are these square matrices always diagonalisable?

My admission is revoked after accepting the admission offer

What is it called when you ride around on your front wheel?

How to translate "red flag" into Spanish?

What is the term for a person whose job is to place products on shelves in stores?

What do you call the part of a novel that is not dialog?

Second order approximation of the loss function (Deep learning book, 7.33)

Retract an already submitted recommendation letter (written for an undergrad student)

Is Electric Central Heating worth it if using Solar Panels?

Will I lose my paid in full property

Could moose/elk survive in the Amazon forest?

Multiple options vs single option UI

How to keep bees out of canned beverages?

A Paper Record is What I Hamper

Arriving in Atlanta after US Preclearance in Dublin. Will I go through TSA security in Atlanta to transfer to a connecting flight?

Why isn't everyone flabbergasted about Bran's "gift"?

What ability score does a Hexblade's Pact Weapon use for attack and damage when wielded by another character?

Why does the Cisco show run command not show the full version, while the show version command does?

How would I use different systems of magic when they are capable of the same effects?

How to not starve gigantic beasts

Could Neutrino technically as side-effect, incentivize centralization of the bitcoin network?

A faster way to compute the largest prime factor

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}

1

$begingroup$

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?

javascript beginner programming-challenge time-limit-exceeded primes

share|improve this question

edited 1 hour ago

200_success

131k17157422

asked 2 hours ago

EagleEagle

1085

New contributor

Eagle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

1

$begingroup$

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?

javascript beginner programming-challenge time-limit-exceeded primes

share|improve this question

edited 1 hour ago

200_success

131k17157422

asked 2 hours ago

EagleEagle

1085

New contributor

Eagle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

$begingroup$

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?

javascript beginner programming-challenge time-limit-exceeded primes

share|improve this question

edited 1 hour ago

200_success

131k17157422

asked 2 hours ago

EagleEagle

1085

New contributor

Eagle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

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

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

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

share|improve this question

edited 1 hour ago

200_success

131k17157422

asked 2 hours ago

EagleEagle

1085

New contributor

Eagle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|improve this question

edited 1 hour ago

200_success

131k17157422

asked 2 hours ago

EagleEagle

1085

New contributor

Eagle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

edited 1 hour ago

200_success

131k17157422

edited 1 hour ago

200_success

131k17157422

asked 2 hours ago

EagleEagle

1085

New contributor

Eagle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 2 hours ago

EagleEagle

1085

2 Answers
2

active

oldest

votes

3

$begingroup$

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

share|improve this answer

answered 1 hour ago

200_success200_success

131k17157422

$endgroup$

add a comment | 

1

$begingroup$

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.

share|improve this answer

answered 56 mins ago

Jorge FernándezJorge Fernández

1645

New contributor

Jorge Fernández is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

Eagle is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f219063%2fa-faster-way-to-compute-the-largest-prime-factor%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

3

$begingroup$

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

share|improve this answer

answered 1 hour ago

200_success200_success

131k17157422

$endgroup$

add a comment | 

3

$begingroup$

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

share|improve this answer

answered 1 hour ago

200_success200_success

131k17157422

$endgroup$

add a comment | 

$begingroup$

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

share|improve this answer

answered 1 hour ago

200_success200_success

131k17157422

$endgroup$

share|improve this answer

answered 1 hour ago

200_success200_success

131k17157422

answered 1 hour ago

200_success200_success

131k17157422

answered 1 hour ago

200_success200_success

131k17157422

1

$begingroup$

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.

share|improve this answer

answered 56 mins ago

Jorge FernándezJorge Fernández

1645

New contributor

Jorge Fernández is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

1

$begingroup$

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.

share|improve this answer

answered 56 mins ago

Jorge FernándezJorge Fernández

1645

New contributor

Jorge Fernández is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

$begingroup$

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.

share|improve this answer

answered 56 mins ago

Jorge FernándezJorge Fernández

1645

New contributor

Jorge Fernández is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|improve this answer

answered 56 mins ago

Jorge FernándezJorge Fernández

1645

New contributor

Jorge Fernández is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered 56 mins ago

Jorge FernándezJorge Fernández

1645

New contributor

Jorge Fernández is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered 56 mins ago

Jorge FernándezJorge Fernández

1645