In the article, we will consider how exactly to find the largest prime factor of a number in python. So, if you ever wondering how exactly really quickly find this number using a programming language or solving the 3rd problem of Project Euler.
Please, continue reading.
What is a prime factor of number?
Ok, wait a minute. Before we just dive into code to find the largest prime factor of a number in python, we need to analyze the core definition of a prime factor number.
Everything comes from the fundamental theorem of arithmetic, which says that every integer greater than 1 has a unique factorization into prime numbers.
But what exactly means “factorization”?
In math, we say that one number(object) has a factorization if we write it as a product of factors usually smaller and the same type. So, if we consider, for example, number: 14. We can write it as a product of smaller numbers 2 and 7 because 2 times 7 is 14. Looks easy.
Now, we know what factorization of numbers is. So, we can continue with a bigger number like for example 20?
We have 4 times 5 is 20, but also 10 times 2 is 20 and 2 times 2 times 5 is 20. Hold a second. We say unique factorization. It makes sense, because, if you continue your analysis you will begin to see that every number have different ways of writing as a product of smaller and the same type numbers.
So, UNIQUE is the key, because you need to have only one way to perform your number in factorization and your numbers cannot be a product of smaller numbers. Those numbers we called prime factors and they are of course natural and greater than 1.
Ok, now we are ready to dive into solving 3rd problem in Project Euler.
Largest Prime Factor – Problem 3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143?https://projecteuler.net/problem=3
First of all, we should find all factors our number. Let’s define a function in python, which takes n number and produce all factors. Then, we can check it for our special cases: 13195 and 600851475143. Every time we use a max function to find the largest factor of a number.
Now, we find our factors and we have put them on a list.
Let’s loop and find the largest prime factor of a number.
Below, you will find a solution how to find the largest prime factor of a number: 13195
And for a number: 600851475143
I hope, that it can be useful to you in some way. If you are curious, about how I solve the 2nd problem go to the link: https://cyberula.com/how-to-find-the-sum-of-even-fibonacci-numbers-using-python-2-project-euler/
Write a comment below, if you find a bug or have a better solution for this problem.