Vjylku

What's parked in Mil Moscow helicopter plant?

Map material from china not allowed to leave the country

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

Israeli soda type drink

"Whatever a Russian does, they end up making the Kalashnikov gun"? Are there any similar proverbs in English?

Would reducing the reference voltage of an ADC have any effect on accuracy?

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

How to open locks without disable device?

How long after the last departure shall the airport stay open for an emergency return?

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

Seek and ye shall find

All ASCII characters with a given bit count

Protagonist's race is hidden - should I reveal it?

Are these square matrices always diagonalisable?

What *exactly* is electrical current, voltage, and resistance?

"Rubric" as meaning "signature" or "personal mark" -- is this accepted usage?

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

What's the difference between using dependency injection with a container and using a service locator?

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

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

std::is_constructible on incomplete types

How to avoid introduction cliches

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

How to keep bees out of canned beverages?

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 55 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 55 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 55 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 55 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 55 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 55 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 55 mins ago

Jorge FernándezJorge Fernández

1645