Projects

Project Euler Problem #3 Complete!

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s