The biggest prime factor
I am trying to make a call to find the largest base ratio 600851475143 . I'm not necessarily asking for an answer. Just trying to figure out why this code is not working. Why is it returning 'undefined' instead of a number?
let isPrime = n => {
let div = n - 1;
while (div > 1) {
if (n % div == 0) return false;
div--;
}
return true;
};
let primeFactor = x => {
for (let i = Math.floor(x / 2); i > 1; i--) {
if (x % i == 0 && isPrime(i) == true) {
return i;
}
}
};
console.log(primeFactor(35)); // 7
console.log(primeFactor(13195)); // 29
console.log(primeFactor(600851475143)); // undefined
source to share
let primeFactor = x => {
if (x === 1 || x === 2) {
return x;
}
while (x % 2 === 0) {
x /= 2;
}
if (x === 1) {
return 2;
}
let max = 0;
for (let i = 3; i <= Math.sqrt(x); i += 2) {
while (x % i === 0) {
x /= i;
max = Math.max(i, max);
}
}
if (x > 2) {
max = Math.max(x, max);
}
return max;
};
console.log(primeFactor(35));
console.log(primeFactor(13195));
console.log(primeFactor(27));
console.log(primeFactor(1024));
console.log(primeFactor(30974914));
console.log(primeFactor(600851475143));
Optimization
-
Dividing a number by 2 until it is odd since an even number is not prime.
-
Increment the iteration
2
, not1
to skip all even numbers. -
The iteration stops at
sqrt(x)
. The explanation for this is here .
source to share
The problem is not with your algorithm, it is perfectly fair, check below the slightly modified algorithm, all I have done is replace your starting point with a Math.floor(x/2)
parameter you can choose:
let isPrime = n => {
let div = n - 1;
while (div > 1) {
if (n % div == 0) return false;
div--;
}
return true;
};
function primeFactor(x, n){
for (let i = n; i > 1; i--) {
if (x % i == 0 && isPrime(i) == true) {
return i;
}
}
}
console.log(primeFactor(35, 35));
console.log(primeFactor(13195, 13195));
console.log(primeFactor(600851475143, 100000))
Using the above, you will get an answer proving that your implementation works, but the loop is too big to do everything (i.e. from Math.floor(600851475143/2)
). Let's say your computer can do 500 million cycles per second, going through each of 300 425 737 571 to 1 takes 167 hours, even at 5 billion cycles per second it takes 16 and a half hours. Your method is extremely inefficient, but will return the correct answer. The reason you are not getting a response on JSBin will most likely be due to browser / service limitations.
More efficient solution spoilers below
The following implementation uses a Sieve of Eratoshenes to generate any list of firmwares and then checks to see if they fully factor into the given number, if you use a large enough list of primes this will work exactly as intended. it should be noted that since it generates a large list of primes it may take some time if it is not started correctly, has to be generated and used for all calls below one list of primes, and the cached list of primes will eventually pay off later do less computation :
function genPrimes(n){
primes = new Uint32Array(n+1);
primes.fill(1)
for(var i = 2; i < Math.sqrt(n); i++){
if(primes[i]){
for(var j = 2*i; j < n; j+=i){
primes[j] = 0;
}
}
}
primeVals = []
for(var i = 2; i < primes.length; i++){
if(primes[i]){
primeVals.push(i);
}
}
return primeVals;
}
function primeFactor(x, primes){
var c = x < primes.length ? x : primes.length
for (var i = c; i > 1; i--) {
if(x % primes[i] == 0){
return primes[i];
}
}
}
primes = genPrimes(15487457);
console.log(primeFactor(35, primes));
console.log(primeFactor(13195, primes));
console.log(primeFactor(600851475143, primes));
console.log(primeFactor(30974914,primes));
source to share