Nov
17
Project Euler: prime factors
Filed Under hisabati, project euler by Mucheru
The best way to learn a programming language is to use it in a project. Having a book is nice as a starting point (and as a reference guide) but I find that you have to step out of the world of tutorials and samples to see new sides of a language and encounter its frustrations. I’ve been meaning to try out python for a while now but I didn’t have a project that I would use it on. Recently, I came across a perfect candidate: Project Euler.
Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.
This is the perfect tool for learning a language that has a functional bent to it.
For my first bit of Python, I tried out problem 3.
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
def unique_prime_factors(n): assert (0 < n) if (n == 1): return [n] factors = [] residue = n divisor = 2 while True: if residue == 1: break while ((residue % divisor) != 0): divisor += 1 factors.append(divisor) while ((residue % divisor) == 0): residue /= divisor return factors
The idea behind the algorithm is pretty straight-forward. Given a number n, check for divisors from 2 to a max number (initially n). Each time we find a divisor, we reduce the max number and use the residue as our new max number. This implicitly caps the size of divisor considered at \sqrt{n} .Also, when we find a factor, we divide the residue for a long as the factor is a divisor thus extracting all the powers of the factor in the residue.
Reducing the residue to the smallest number we need speeds up our algorithm and proves to be a great boost in performance if we the number we’re factoring has small factors (i.e. is B-smooth for a small B).