Skip to content

Instantly share code, notes, and snippets.

@nefarioustim
Created July 31, 2012 09:34
Show Gist options
  • Save nefarioustim/3215506 to your computer and use it in GitHub Desktop.
Save nefarioustim/3215506 to your computer and use it in GitHub Desktop.
Find the largest prime factor of a composite number
var x = 600851475143,
getLargestPrimeFactor = function(n) {
var largestPrimeFactor,
factor = 2;
while (n > 1) {
if (n % factor === 0) {
largestPrimeFactor = factor;
n = n / factor;
while (n % factor === 0) {
n = n / factor;
}
}
factor += (factor === 2) ? 1 : 2;
}
return largestPrimeFactor;
};
console.log(getLargestPrimeFactor(x));
var x = 600851475143,
isPrime = function(n) {
if (n === 2) return true;
if (n % 2 === 0) return false;
for (var factor = 3; factor <= Math.sqrt(n); factor += 2)
if (n % factor === 0) return false;
return true;
},
getLargestPrimeFactor = function(n) {
var largestPrimeFactor;
for (var factor = 2; factor <= Math.sqrt(n); factor++)
if (n % factor === 0 && isPrime(factor))
largestPrimeFactor = factor;
return largestPrimeFactor;
};
console.log(getLargestPrimeFactor(x));
@bastianwegge
Copy link

You could use an array instead and use array.push(largestPrimeFactor); after line 8. This would create an array with the prime factors.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment