Euler 3

Project Euler 3

by bshourd

JavaScript

/*
 * Project Euler 3: http://projecteuler.net/problem=3
 * What is the largest prime factor of the number 600851475143 ?
 */

// Returns largest prime factor of num
// If num cannot be dealt with, returns -1
var euler3 = function(num) {
    // Finds smallest factor of num bigger than 
    // or equal to start
    var factor = function(num, start) {
        // Only need to check odds, but if start is even, check it first
        if (start % 2 === 0) {
            if (num % start === 0) {
                return start;
            }
            start++;
        }
        for (var i = start; i < Math.sqrt(num); i += 2) {
            if (num % i === 0) {
                return i;
            }
        }
        return num;
    };
    
    var start = 2;
    // Keep reducing until we are done
    while (num !== 1) {
        start = factor(num, start);
        num /= start;
    }
    return start;
};

console.log(euler3(600851475143));