Problem #3 asks: “What is the largest prime factor of the number 600,851,475,143?” Barring a naive, “brute-force” approach, the real question becomes: “How can we decompose any number, n, into prime factors?” I approached the problem by deciding to iterate through 2 and the rest of the odd naturals less than sqrt(n). Again, simply trying all the odds seemed elementary, so I employed an Euclid-esque technique that removes each found factor from n, then tests n again before moving to the next odd. This loop continues until the remainder is less than the odd number to be tested. By using the remainder for the loop’s terminating condition, the number of iterations is significantly reduced in cases where prime factors are found early. In cases where n is the product of two primes close in value, the overall performance gets closer to iterating naively to sqrt(n).
Here’s my code via codepad.org: http://codepad.org/9nFYLr3B
bowdenc 