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;
}
$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
primesto store all the prime numbers less thannumberLoop through the odd numbers only below
numberto check for primes usingi
Check if
iis divisible by any of the elements already inprimes.
- If yes,
isPrime = falseand break the for loop forjbyj=primesLength
- If not,
isPrime = true
- If yes,
If
isPrime == truethen addito the arrayprimesand check ifnumber%i == 0
- If
number%i == 0%update the value offactorasfactor = i
- If
Return
factorafter looping through all the numbers belownumber
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
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
primesto store all the prime numbers less thannumberLoop through the odd numbers only below
numberto check for primes usingi
Check if
iis divisible by any of the elements already inprimes.
- If yes,
isPrime = falseand break the for loop forjbyj=primesLength
- If not,
isPrime = true
- If yes,
If
isPrime == truethen addito the arrayprimesand check ifnumber%i == 0
- If
number%i == 0%update the value offactorasfactor = i
- If
Return
factorafter looping through all the numbers belownumber
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
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
primesto store all the prime numbers less thannumberLoop through the odd numbers only below
numberto check for primes usingi
Check if
iis divisible by any of the elements already inprimes.
- If yes,
isPrime = falseand break the for loop forjbyj=primesLength
- If not,
isPrime = true
- If yes,
If
isPrime == truethen addito the arrayprimesand check ifnumber%i == 0
- If
number%i == 0%update the value offactorasfactor = i
- If
Return
factorafter looping through all the numbers belownumber
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
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$
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
primesto store all the prime numbers less thannumberLoop through the odd numbers only below
numberto check for primes usingi
Check if
iis divisible by any of the elements already inprimes.
- If yes,
isPrime = falseand break the for loop forjbyj=primesLength
- If not,
isPrime = true
- If yes,
If
isPrime == truethen addito the arrayprimesand check ifnumber%i == 0
- If
number%i == 0%update the value offactorasfactor = i
- If
Return
factorafter looping through all the numbers belownumber
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
javascript beginner programming-challenge time-limit-exceeded primes
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
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
edited 1 hour ago
200_success
131k17157422
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
asked 1 hour ago
EagleEagle
1085
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.
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.
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 |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
There are many questions about Project Euler 3 on this site already. The trick is to pick an algorithm that…
- Reduces
nwhenever 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_success200_success
131k17157422
$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.
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.
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
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
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There are many questions about Project Euler 3 on this site already. The trick is to pick an algorithm that…
- Reduces
nwhenever 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_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
nwhenever 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_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
nwhenever 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_success200_success
131k17157422
$endgroup$
There are many questions about Project Euler 3 on this site already. The trick is to pick an algorithm that…
- Reduces
nwhenever 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_success200_success
131k17157422
answered 1 hour ago
200_success200_success
131k17157422
answered 1 hour ago
200_success200_success
131k17157422
answered 1 hour ago
200_success200_success
131k17157422
131k17157422
add a comment |
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.
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.
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.
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$
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á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
answered 43 mins ago
Jorge FernándezJorge Fernández
1645
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.
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.
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 |
add a comment |
Eagle is a new contributor. Be nice, and check out our Code of Conduct.
Eagle is a new contributor. Be nice, and check out our Code of Conduct.
Eagle is a new contributor. Be nice, and check out our Code of Conduct.
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.
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
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
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
