Ryfujk

How to open locks without disable device?

A faster way to compute the largest prime factor

The art of proof summarizing. Are there known rules, or is it a purely common sense matter?

Married in secret, can marital status in passport be changed at a later date?

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

Trumpet valves, lengths, and pitch

A Dictionary or Encyclopedia of Fantasy or Fairy Tales from the 1960s

What's parked in Mil Moscow helicopter plant?

Why did Israel vote against lifting the American embargo on Cuba?

What is the best way to deal with NPC-NPC combat?

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

Is there any hidden 'W' sound after 'comment' in : Comment est-elle?

Does Mathematica have an implementation of the Poisson binomial distribution?

What is this word supposed to be?

Can I criticise the more senior developers around me for not writing clean code?

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

How to not starve gigantic beasts

As an international instructor, should I openly talk about my accent?

Did the Roman Empire have penal colonies?

How do I check if a string is entirely made of the same substring?

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

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

Is it acceptable to use working hours to read general interest books?

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

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 1 hour 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 1 hour 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 1 hour 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 1 hour 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 1 hour 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 1 hour 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 1 hour 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 43 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 43 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 43 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 43 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 43 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 43 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 43 mins ago

Jorge FernándezJorge Fernández

1645