Hello everyone! Today we're going to look at prime numbers. So, what exactly is a prime number? Any number that is only divisible by itself, and 1 is a prime number. 3, for example, would be a prime number. And so would 5, 7, 11, 13, etc. The prime factorization of a number means breaking down any number, into its basic prime factors, i.e. 10 = 5 * 2, 5 and 2 both being prime, are the prime factors of 10. But why does this matter? Why would I ever need a number that's only divisible by itself? The answer is that it allows us to create mathematical locks. Suppose I were to take two large random prime numbers, P1 = 761, and P2 = 829. If I multiply these numbers together I get 630869, which is not a prime number in and of itself, HOWEVER, if I were to then ask you for the prime factorization of that number (without you knowing P1 and P2, obviously) that would be a very difficult problem to solve! And as the numbers get larger, the time it takes to solve grows exponentially. This is the concept behind the RSA encryption standard. Now, onto the problem!
The prime factors of 13195 are 5, 7, 13 and 29.What is the largest prime factor of the number 600851475143 ?
Let's call 600851475143 p. The most important thing to remember during this is that the largest prime factor will always be smaller than the square root of p. This is going to save us a lot of time. We're also going to use while loops in this problem. While loops will run so long as they are true.
Consider the following:
x=1
while x=1 while x<2
print("Hi") print("Hi")
x += 1
The first example will run forever, while the second will only run once. After one iteration, x = 2, the condition x < 2 is no longer met.
Here's the code that we're going to use to find the largest prime factor
p = 600851475143 #our prime number
n = 2 #our potential factor
while n * n < p:
while p%n == 0:
p = p / n
n = n + 1
print (p)Our first while loop, n * n < p: is based on the concept stated before that the largest prime factor will always be smaller than the square root of p. After this loop is executed, we increase n by 1. Our second while loop says that while our prime number is evenly divisible by our potential factor, we replace our prime number, with that result, and we repeat the process with that number.
Suppose p = 21; 2*2 < 21, but 21 is not evenly divisible by 2. 2 now becomes 3. 3*3 < 21, 21 is evenly divisible by 3, 21/3 = 7, 7 is not evenly divisible by 3, breaking our inner while loop. 7 * 7 is not less than 21, breaking our outer while loop, therefore printing our largest prime factor n, which for the case of 21 would be 7.
If we scale this concept up to our original prime number of 600851475143 we find that the largest prime factor of the number is 6857!
I tried to make this as accessible as possible, but if you have any questions please feel free to leave a comment and I'll do my best to clarify!