Three Coding Challenges

Largest Prime Factor, Largest Palindrom Product and 10001st Prime

Posted on September 10, 2016 as Programming. 7 minutes read.

Introduction

Hi, today we're gonna explore more about programming and math. I've chosen 3 challenges from Project Euler- Largest Prime Factor of a number, Largest Palindrom and 10001st Prime. Project Euler is a great site that provides us with many mathematical/programming problems that will undoubtedly help us gain a better insight in beautiful word of mathematics and programming.

I strongly encourage you to come up with your own ideas as you will learn more than just by reading about this. I have spent quite a few hours working on the solutions and I can say without hesitation, that the feeling after finishing the task is amazing. But let's move on to the tasks! ;)

Largest Prime Factor

In this task we are assigned to find the largest prime factor of a number 600851475143. Quite a big one, right?

Firstly let's see how finding prime factors works on some smaller number, let's say 12.

  1. Divide the number by the smallest prime number which is 2 | 12 / 2 = 6 | Prime factor = 2
  2. Divide the the previous result by 2 | 6 / 2 = 3 | Prime factor = 2 and Prime factor = 3
  3. Prime factors of number 12 are 2 , 2, 3 because 12 = 2 * 2 * 3

If you still don't know how it works let's see another example - number 147

  1. In this example dividing by 2 will not work beacuse 147 / 2 = 73,5 so let's change divider to the next prime number which is 3 | 147 / 3 = 49 | Prime factor = 3
  2. Now let's try factoring 49. Smallest number that will work is 7. | 49 / 7 = 7 | Prime factor = 7 and Prime factor = 7
  3. Prime factors of number 147 are 3 , 7, 7 because 147 = 3 * 7 * 7

But how to implement it with python code? That's my solution.

def prime_factors(x):
    a = 2
    factors = []
    while a * a <= x:
        if x % a:
            a += 1
        else:
            x //= a
            factors.append(a)
    if x > 1:
        factors.append(x)
    return factors

factors = prime_factors(600851475143)

print(factors)
print(max(factors))

Firstly we define the variable a which is starting value of our divider and list factors that will hold our prime factors. Then inside of the while loop we are checking if our desired number is divisible by a, if not we're adding 1 to a, if yes we're adding a to the list of factors and we're changing number x into the x // a. At the end of the loop, program will return list of factors, and then print the biggest one using max function.

$ python3 prime_factors.py
[71, 839, 1471, 6857]
6857

Largest Palindrom Product

Palindrom is a number that is read the same from the beginning as from the end, for example 2506052. In this task our goal is to find the largest palindrome made from the product of two 3-digit numbers. For me the hardest thing is to check if the number is the same from it's beginning as from it's end because generating such a number will be just brute forcing every combination.

def find_palindrome():
    largest = 0
    for i in range (100, 999):
        for r in range(100, 999):
            x = str(i * r)
            y = x[::-1]
            if x == y:
                x = int(x)
                if x > largest:
                    largest = (x)
    return largest

def main():
    print(find_palindrome())

if __name__ == '__main__':
    main()

Firstly we're going to create a range for both of the numbers i and r from 100 to 999 (minimal and maximal 3 digit number). Then x is going to be the result of multiplying both of these numbers i and r and it's going to be our palindrome - yet we need to check if it's really palindrome. But how to check it? I used x[::-1] which will generate string in the reverse order. Here's how it works:

>>> string = "1234"
>>> print(string[::-1])
4321

Then if the number is equal to its reverse version we're changing it into the integer and assigning it to the variable largest. Last part of the code will check whether or not the palindrome is the largest, if not, it's going to generate the bigger one, if yes, then it's getting printed.

$ python3 palindrome.py
906609

10001st Prime

And here comes the last one. We have to find the 10001st prime number. By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. After thinking for a while I came up with this simple solution to the problem using previous prime_factors function. Prime number is only divisible by itself and 1. So there's going to be only one factor of this number - itself. That's how I want to check whether or not it's a prime number. Let's take a look at the code.

def prime_factors(x):
    a = 2
    factors = []
    while a * a <= x:
        if x % a:
            a += 1
        else:
            x //= a
            factors.append(a)
    if x > 1:
        factors.append(x)
    return factors


def generate():
    exists = False
    number = 0
    counter = 0
    while not exists:
        number += 1
        factors = prime_factors(number)
        if len(factors) == 1 and factors[0] == number:
            counter += 1
            if counter == 10001:
                print(number)
                exists = True
        else:
            pass
if __name__ == '__main__':
    generate()

We're using our previous function to generate prime factors of a number. In the generate() function loop is going to iterate numbers from 1 until we find desired prime number, then the loop is going to stop. Counter will allow us to see which prime number it is. Then if there is only one factor and it's value is the same as the number counter is incrementing by one. After that, when the counter reaches 10001st number, program will print the result and loop will end. Quite simple, right?

$ python3 prime_10001.py
104743

Github

And that's the last one. I strongly encourage you to try other tasks as I'm sure that it will significantly improve your programming and mathematical knowledge. As always thanks for reading, it really motivates me to write more about. Good luck!

Keep learning and stay safe!

~ W3ndige