Categories
Uncategorized

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.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s