Saturday, February 28, 2015

Project Euler - Largest prime factor


The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

https://projecteuler.net/problem=3


My comments: So, this was a very interesting problem to do. Solving the problem for small numbers took me about 2 minutes. HOWEVER, realizing that my computer was brute forcing it and trying to deal with the larger number and NOT coming to a solution withing a reasonable time (10+ mins is about when I gave up on waiting) made me realize I needed to change how it was working. By making it iterate fewer times the brute force gives a "instant" answer if you only have to iterate up to the square root of the number in question. So for example, let's say we have a number 64. The square root is 8. So we can iterate only up to 8 and find out that 1, 2, 4, and 8 are the only factors.. and we can get the other side of the factor by diving the number (64) over those 4 values. So we know that 1 goes with 64, 2 goes with 32, 4 goes with 16, and 8 goes with 8.. and then from there we can only take the ones of those that are prime. As opposed to just iterating from 1 to n, which takes a very very long time and is extremely inefficient.