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.