# Project Euler: prime factors

Filed Under hisabati, project euler by | 1 Comment

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).

← Previous Page