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
What *exactly* is electrical current, voltage, and resistance?
How to not starve gigantic beasts
"Rubric" as meaning "signature" or "personal mark" -- is this accepted usage?
What is the least dense liquid under normal conditions?
I preordered a game on my Xbox while on the home screen of my friend's account. Which of us owns the game?
Why does the Cisco show run command not show the full version, while the show version command does?
What do you call the part of a novel that is not dialog?
Did the Roman Empire have penal colonies?
Has a Nobel Peace laureate ever been accused of war crimes?
Check if a string is entirely made of the same substring
Is accepting an invalid credit card number a security issue?
The art of proof summarizing. Are there known rules, or is it a purely common sense matter?
What is the best way to deal with NPC-NPC combat?
How can I wire a 9-position switch so that each position turns on one more LED than the one before?
My admission is revoked after accepting the admission offer
Implementing 3DES algorithm in Java: is my code secure?
c++ diamond problem - How to call base method only once
Are there moral objections to a life motivated purely by money? How to sway a person from this lifestyle?
How would this chord from "Rocket Man" be analyzed?
What is it called when you ride around on your front wheel?
What's the difference between using dependency injection with a container and using a service locator?
Seek and ye shall find
What is a 'Key' in computer science?
With indentation set to `0em`, when using a line break, there is still an indentation of a size of a space
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
primes
to store all the prime numbers less thannumber
Loop through the odd numbers only below
number
to check for primes usingi
Check if
i
is divisible by any of the elements already inprimes
.- If yes,
isPrime = false
and break the for loop forj
byj=primesLength
- If not,
isPrime = true
- If yes,
If
isPrime == true
then addi
to the arrayprimes
and check ifnumber%i == 0
- If
number%i == 0%
update the value offactor
asfactor = i
- If
Return
factor
after 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
New contributor
$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 thannumber
Loop through the odd numbers only below
number
to check for primes usingi
Check if
i
is divisible by any of the elements already inprimes
.- If yes,
isPrime = false
and break the for loop forj
byj=primesLength
- If not,
isPrime = true
- If yes,
If
isPrime == true
then addi
to the arrayprimes
and check ifnumber%i == 0
- If
number%i == 0%
update the value offactor
asfactor = i
- If
Return
factor
after 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
New contributor
$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 thannumber
Loop through the odd numbers only below
number
to check for primes usingi
Check if
i
is divisible by any of the elements already inprimes
.- If yes,
isPrime = false
and break the for loop forj
byj=primesLength
- If not,
isPrime = true
- If yes,
If
isPrime == true
then addi
to the arrayprimes
and check ifnumber%i == 0
- If
number%i == 0%
update the value offactor
asfactor = i
- If
Return
factor
after 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
New contributor
$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
primes
to store all the prime numbers less thannumber
Loop through the odd numbers only below
number
to check for primes usingi
Check if
i
is divisible by any of the elements already inprimes
.- If yes,
isPrime = false
and break the for loop forj
byj=primesLength
- If not,
isPrime = true
- If yes,
If
isPrime == true
then addi
to the arrayprimes
and check ifnumber%i == 0
- If
number%i == 0%
update the value offactor
asfactor = i
- If
Return
factor
after 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
New contributor
New contributor
edited 1 hour ago
200_success
131k17157422
131k17157422
New contributor
asked 1 hour ago
EagleEagle
1085
1085
New contributor
New contributor
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
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).
$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.
New contributor
$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
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).
$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).
$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).
$endgroup$
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_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.
New contributor
$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.
New contributor
$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.
New contributor
$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.
New contributor
New contributor
answered 45 mins ago
Jorge FernándezJorge Fernández
1645
1645
New contributor
New contributor
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