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:

Post a Comment