Categories

Finding Prime Numbers – Python

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.