A faster way to compute the largest prime factor Announcing the arrival of Valued Associate...

finding a tangent line to a parabola

Map material from china not allowed to leave the country

Is a 5 watt UHF/VHF handheld considered QRP?

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

Why didn't the Space Shuttle bounce back into space as many times as possible so as to lose a lot of kinetic energy up there?

I preordered a game on my Xbox while on the home screen of my friend's account. Which of us owns the game?

How to avoid introduction cliches

Prove the alternating sum of a decreasing sequence converging to 0 is Cauchy.

Check if a string is entirely made of the same substring

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

Can you stand up from being prone using Skirmisher outside of your turn?

How to use @AuraEnabled base class method in Lightning Component?

Does Feeblemind produce an ongoing magical effect that can be dispelled?

A strange hotel

PIC mathematical operations weird problem

Trumpet valves, lengths, and pitch

Justification for leaving new position after a short time

Is Electric Central Heating worth it if using Solar Panels?

Are there moral objections to a life motivated purely by money? How to sway a person from this lifestyle?

Co-worker works way more than he should

What is a 'Key' in computer science?

Is Bran literally the world's memory?

Passing args from the bash script to the function in the script

Raising a bilingual kid. When should we introduce the majority language?

A faster way to compute the largest prime factor

Announcing the arrival of Valued Associate #679: Cesar Manara

Unicorn Meta Zoo #1: Why another podcast?Project Euler #3 - largest prime factorFaster way to determine largest prime factorx64 Assembly - checking for largest prime factorProject Euler #3 (Largest prime factor) in SwiftProject Euler 3: Getting the largest prime factor of a numberVery slow Project Euler Q3 (largest prime factor of a large number)Project Euler 3: Largest prime factorLargest prime factor of a given numberProject Euler 3 - Largest prime factorEuler problem 3: largest prime factor of the numberWork out largest prime factor of a number

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

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?

edited 1 hour ago

200_success

131k17157422

asked 1 hour ago

Eagle

1085

New contributor

add a comment |

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?

edited 1 hour ago

200_success

131k17157422

asked 1 hour ago

Eagle

1085

New contributor

add a comment |

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?

edited 1 hour ago

200_success

131k17157422

asked 1 hour ago

Eagle

1085

New contributor

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?

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

javascript beginner programming-challenge time-limit-exceeded primes

edited 1 hour ago

200_success

131k17157422

asked 1 hour ago

Eagle

1085

New contributor

edited 1 hour ago

200_success

131k17157422

asked 1 hour ago

Eagle

1085

New contributor

edited 1 hour ago

200_success

131k17157422

edited 1 hour ago

200_success

131k17157422

edited 1 hour ago

200_success

131k17157422

asked 1 hour ago

Eagle

1085

New contributor

asked 1 hour ago

Eagle

1085

asked 1 hour ago

Eagle

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.

add a comment |

2 Answers
2

active

oldest

votes

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

answered 1 hour ago

200_success

131k17157422

add a comment |

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.

answered 43 mins ago

Jorge Fernández

1645

New contributor

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

Post as a guest

Name

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

Required, but never shown

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

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.

answered 1 hour ago

200_success

131k17157422

add a comment |

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.

answered 1 hour ago

200_success

131k17157422

add a comment |

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.

answered 1 hour ago

200_success

131k17157422

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.

answered 1 hour ago

200_success

131k17157422

answered 1 hour ago

200_success

131k17157422

answered 1 hour ago

200_success

131k17157422

answered 1 hour ago

200_success

131k17157422

add a comment |

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.

answered 43 mins ago

Jorge Fernández

1645

New contributor

add a comment |

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.

answered 43 mins ago

Jorge Fernández

1645

New contributor

add a comment |

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.

answered 43 mins ago

Jorge Fernández

1645

New contributor

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.

answered 43 mins ago

Jorge Fernández

1645

New contributor

answered 43 mins ago

Jorge Fernández

1645

New contributor

answered 43 mins ago

Jorge Fernández

1645

answered 43 mins ago

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

add a comment |

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

draft saved

draft discarded

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

Thanks for contributing an answer to Code Review Stack Exchange!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

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

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

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

Post as a guest

Name

Required, but never shown

Sign up or log in

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

Post as a guest

Name

Required, but never shown

Sign up or log in

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

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Gsyfuy