Problem 3 from the Project Euler website.

## The Problem

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

## My Solution

WARING: It’s right…but not efficient at all.

Don’t use – your computer will hate you.

I’ll come back to this one when I suck less at Python.

We can start by testing individual numbers to see if they’re prime or not.

# Let's try it with 8 first... var=8 # we set 'prime' boolean to True prime=True # we start from 2, so that it doesn't check for 1 for x in range(2,var): # test for remainder test1=float(var)/float(x) test2=var/x # if there's no remainder if test1-test2==0: #changes 'prime' to False, meaning it's not a prime number prime=False # so if prime is set to 'False' then it will print 'never mind' if prime==False: print "Never Mind" # otherwise, it will print 'We're good!' else: print "We're good!"

This should return

`Never Mind`

…since 8 is not a prime number. But we know it works!

If we do it for the number 7, we should get

`We're good!`

since it is a prime number.

Now we create another loop to test a range of number, rather than one at a time.

It would also be a good idea to clean it up a bit too…

# we limit the first range from 1 to 20 just while we test for var in range(1,20): prime=True for x in range(2,var): if float(var)%float(x)==0: prime=False if prime==True: print var,

that returns

`2 3 5 7 11 13 17 19`

Now we can make it into a function so we can change the range of numbers to test.

# The 'st' variable is range start, and # the 'nd' variable is our limit. def finPri(st,nd): for var in range(st,nd): prime=True for x in range(2,var): if float(var)%float(x)==0: prime=False if prime==True: print var, # we call it with... finPri(1,50)

That returns

`1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47`

It works!!

We can now add the bit that will check the multiples of the digit…

# We declare a list so we can put all correct answers there listd=[] def finPri(st,nd): for var in range(st,nd): prime=True for x in range (2,var): if float(var)%float(x)==0: prime=False if prime==True: # Here we check if they are multiples if float(nd)%float(var)==0: # If they are then we add them to the list listd.append(var) # Then we print the last digit of the list print listd[-1] # we are going to test with the above example finPri(1,13195)

All of this should return

`29`

There we go!

DONE!

Like I said before, it works with small numbers, but not with 600,851,475,143.

Don’t try it.