profile for Kells1986 at Stack Overflow, Q&A for professional and enthusiast programmers

Wednesday, 28 November 2012

Project Euler Q3 & Q4

OK, so moving on with the project Euler questions, we're up to question 3, which is where things start to get challenging.

Question 3 asks:


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

What is the largest prime factor of the number 600851475143 ?

So, to solve this problem we're going to need a good way of generating primes. One fairly efficient way of doing this is to use an algorithm called the Sieve of Eratosthenes. This algorithm works by removing multiples of primes that have already been identified, this reduces the number of candidates that are possible prime numbers.

To illustrate this, consider the numbers 2 - 10:
2  3  4  5  6  7  8  9  10

obviously 2 is prime, so no other multiple of 2 can be prime. That leaves the list looking as follows:
2  3  4  5  6  7  8  9  10 

now 3 is tested against 5, 7 and 9, removing 9. Then all the primes below 10 have been found.

The following code is a Python prime number generator that uses the Sieve of Eratosthenes to find prime numbers:



def gen_primes():
    D = {}  

    # The running integer that's checked for primeness
    q = 2  

    while True:
        if q not in D:
            yield q        
            D[q * q] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]

        q += 1

Using this code we can now test which primes divide the large number provided by PE.

number=600851475143
divisors=[]

for prime in gen_primes():
        
        if(number%prime == 0):
                divisors.append(prime)
                number = number/prime           

        if (prime >= number):
                break

print max(divisors)

The code adds all the primes that divide the large number exactly into a list. At the end of the loop the largest divisor is printed to the screen. For this question the answer is 6857.


Next up is question 4, which asks:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

My approach to this question was somewhat brute-force. I defined a function to test if a number was a palindrome by converting it to a string and using some of Python's built-in string manipulation tools. The source code for this function is given below:

  def is_palindrome(number):
        forward=str(number)
        backward=forward[::-1]

        if forward == backward:
                return True
        else:
                return False
so the code is pretty simple, convert the number to a string (called forward). reverse the string with the command backward=forward[::-1], and compare the resulting two strings. If forward is the same as backward then obviously we have a palindrome.

Then I just tested every combination of three digit numbers, storing the results that were palindromes. The following code outlines my method:

pals=[]
for num1 in xrange(100,1000):
        for num2 in xrange(100, 1000):
                prod = num1*num2
                if is_palindrome(prod):
                        pals.append(prod)


print max(pals)

I need to have nested loops to make sure I test all the combinations, even if I will test some combinations twice. This brute-force algorithm still runs pretty quickly on my laptop, producing a result in a couple of seconds. The answer, incidentally, is 906609.

Thanks for reading. If you've got any comments/suggestions, or you want to share your solution, please leave a comment at the bottom of the page.
 


No comments:

Post a Comment