Friday, August 15, 2008

Diving into python and projecteuler

While solving a trivial problem presented at ProjectEuler, I went for python instead of C, which is my usual language of preference. I am quite new in python programming though, hence the interest in applying my newly accuired skills.

The problem was pretty straightforward,
What is the largest prime factor of the number 600851475143 ?

Now considering the number being too big and my new found interest in python, it was an obvious choice. So, here is my solution,

#!/usr/bin/env python
import math

NUMBER = 600851475143
i=int(math.sqrt(NUMBER))

while i>1:
if not (NUMBER%i): # so i is a factor of NUMBER
# checking if i is prime
flag = 0
if not ((i+1)%6) or not ((i-1)%6):
for j in range (2,int(math.sqrt(i))+1):
if not (i%j):
flag = 1
break
else:
flag = 1
if not flag: # i is prime, so i is the answer
break
i -= 1
print "The largest prime factor is %d" % i


All this while, when I was reading about python, I kept stumbling into language purists who would say that interpreted languages are no good and that they take up too much time. Hence I put my code to the time test and this is the result,

[ProjectEuler]$ time python 003_problem.py
The largest prime factor is 6857

real 0m0.827s
user 0m0.816s
sys 0m0.006s
[ProjectEuler]$


I think, considering the hassle of computing big numbers like this one in other languages, specially ones like C, and the fact that it still gets interpreted in about 0.827 seconds speaks volumes about its power. For all I know, experienced python programmers might still be able to improve the solutions.

0 Comments: