Tag: Prime Factorization

Hello all!

It’s been a while since I last posted, apologies. I’ll be doing another Project Euler problem today.

Problem 3:

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

What is the largest prime factor of the number 600851475143 ?

I’d like to begin by saying that I spent way too long on this problem improving my code after I had already solved it. But this is a very good mindset to have when you are trying to become better at something. Due to the increased complexity of this problem, it is a good idea to write an algorithm for it, and I will likely do this for all future problems.

def largest_prime(n)
  Iterate through each number up until the square root of n
    If the iterable is prime and the modulo of the base and iterable is 0:
      Append the iterable to some empty list
  print the [-1] element of the list, and this is the largest prime

I decided on an algorithm where I will check every number’s divisibility and ‘prime-ness’ up until the square root of the original number. This works because you can have no prime factor larger than the square root of the number. Next, I add every valid number to some list, and then I go back and pick out the largest one from the list and this is the answer’s problem. Now I need to turn this into working code, and then from there, I can improve it.

def largest_prime(base):
  primes = []
  root = math.sqrt(base)
  for i in range(int(root+1)):
    if is_prime(i) == True and base%i == 0:
      primes.append(i)
  prime = primes[-1]
  print(prime)
  print(primes)

In theory, this code should work but now I need to make a function is_prime(n) that allows me to check if a number is prime for some boolean value. I’ll do this by checking every number up until the square root for divisibility, and if I find no divisibility other than 1 and the number itself then I will declare the number as prime.

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, (int(math.sqrt(n))+1)):
        if n%i == 0:
            return False
    return True

Although all of this code works, it is very inefficient. If I insert a timer using from time import * my code takes an average of roughly 7 seconds to run. I would like to cut this down to 1 second or less in any way I can. One way I can optimize the code is by removing my use of lists, but this only saves me ~1 second. This is where I’ll introduce recursion into my programming repertoire. Recursion is when you have a function that calls on itself repeatedly until the task is done. When the task is done the look breaks and returns your answer.

In order to do this problem using recursion, I have to redefine my algorithm. Instead of using another function is_prime(n) I’ll be taking each number, finding the lowest common divisor. I will then take this new number, (n/lcd), and perform the same method on it until I can no longer be divided and this final number is our largest prime factor.

def largest_prime(base):
  start = clock()
  for i in range(2, int(math.sqrt(base)+1)):
    if base % i == 0:
      return largest_prime(base/i)
  print(base)
  end = clock()
  print(end-start)

This is my final piece of code and it takes ~0.0008 seconds to run. I am very happy with the results as the code is simple and condensed. I’d like to end this post by talking about mindsets and why they matter. When you’re trying to get better at something you should realize that your abilities are not as fixed as you think they are. I see this problem a lot in my high school, kids in my Pre-Calculus class often complain that they are bad at math but then when they like a topic we are learning in the class they do extremely well at it because they enjoy it and put effort into it. A good analogy of this is someone learning to play an instrument. When you’re practicing hitting higher notes on a trumpet you don’t squeak a note and say “I’m bad at this and I should just give up trumpet” you instead say “Okay, I need to put faster air through the trumpet” and you try again, so why not do this with other things you are trying to get good at? If you would like to know some more about mindsets I highly recommend Mindset: The New Psychology of Success by Carol Dweck. It details lots of information and research about growth mindsets and how they can improve your life.

Thanks for reading and have a wonderful day!
~ Corbin