Project Euler is a website with a series of math problems that can be solved with programming. Problem 3 is about finding the largest prime factor of a number.
Although my first impression is that the problem looks simple since I can iterate through the possibilities one by one and find the largest prime factor.
The problem is that we’re finding the largest prime factor!
The largest prime factor of a very large number can be as big as the number itself, and I can run of memory if I test every number one by one!
I need to do something more.
What can we do to speed up the process of finding the largest prime factor?
A decent solution
I like to use Python, so I’ll show a decent answer in Python.
def lpf(a):
b = 2
while (a > b):
if (a % b == 0):
a = a / b;
b = 2;
else:
b += 1;
print("Largest Prime Factor: %d" % (b))
I start b at 2 because we aren’t considering 1. If there aren’t any factors at all, then the largest prime factor would be the number itself.
The largest prime factor of a prime number is the number itself.
We have to consider composite numbers though.
I know that the condition for finding the largest prime factor of a composite number is that the factor has to be lower than the number that we’re testing.
a = the number b = largest prime factor
a > b if we're dealing with a composite number.
To check if a big number is divisible by a smaller number, you can check if the division equals 0 with modulo.
a % b == 0
If a is divisible by b, then we can break down a by dividing by b.
Every time we divide a by b, the smaller a becomes a factor of the original a.
We keep redoing this process of dividing the composite numbers by b because we will eventually hit a point where we cannot break down a anymore.
At the point where we find an a that cannot be divided cleanly is when we get the prime number that we’re looking for.
Why does this work? I’ll try to explain as best as I can in text.
We reset b to 2 constantly because b is just a tool to check for a's primality.
If the current a manages to be divisible by a b, we divide the a, and thus, we have to check the new a’s primality.
Let’s say we have 10.
10 % 2 == 0.
Now, let’s break down 10 to 5 because we divide a by the divisible number, b, which happens to be 2.
5 % 2 != 0 5 % 3 != 0 5 % 4 != 0 5 == 5, so here we stop.
5 is the largest prime factor.
If a is not prime, then we break a down by b. To reiterate, b is a tool for us to check primality.
If the a happens to be prime, then we know that the number is the largest prime factor since we’re walking through the problem backwards from larger to smaller prime factors of a.
We break down the root that is a into smaller a's by dividing by b until a is a prime number.
Every a on each division will certainly be a factor of the original a.
Since the while loop checks if every a is prime, we will know that a will eventually be prime. We’re going backwards from the original largest a to smaller and smaller a’s!
We will eventually reach the largest prime factor when a is no longer divisible by any b.
What is the largest prime factor of the number 600851475143 ?
Answer: 6857
Time complexity: log b (n)