## Project Euler 003 – JavaScript

18 02 2011

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Solution

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"&gt;

<html xmlns="http://www.w3.org/1999/xhtml"&gt;

<title>Project Euler 003</title>

<body >

<script type="text/javascript">

function PrimeFactor(number)

{

//here is our list of prime factors

factors = new Array();

//assume the number is prime

//unless we find a factor

isPrime = true;

//here is the upper limit of what we need to test

factorCandidate = Math.round(Math.sqrt(number), 0);

while (factorCandidate > 1)

{

//is this a factor?

if (number % factorCandidate == 0)

{

//if so, what are it’s factors?

divisor = number / factorCandidate;

factors.concat(PrimeFactor(factorCandidate));

factors.concat(PrimeFactor(divisor));

isPrime = false;

}

//next

factorCandidate–;

}

//we are only adding prime factors

if (isPrime) { factors.push(number); }

return factors;

}

factors = PrimeFactor(600851475143);

// this sorts the numbers in ascending order

factors.sort();

// this reverses the list so the biggest one

// is on top.

factors.reverse();

</script>

</body>

</html>

Discussion

Debugging JavaScript is not my forte.  The concat function was handy here, but I don’t think that JavaScript is going to get much better for me unless I spend some time getting better tools.