_{Links: Project Euler, HackerRank}

### Problem statement:

We need to find the largest prime factor for given $N$ , where $10 \le N \le 10^{12}$ , and for Project Euler, $N$ is $600851475143$ .

### Solution:

My strategy is to pre-calculate the list of prime numbers until the maximum `N`

and then just calculate the largest prime factor from the list for each `N`

.

A prime number is a number that is divisible only by
$1$
and itself. So the simple algorithm to identify if the number is a prime number should be:

```
def is_prime(num: int) -> bool:
if num <= 1: return False
# We need to check divisibility till the square root of N
# see https://stackoverflow.com/a/5811176/8010366
till = math.floor(math.sqrt(num)) + 1
for div in range(2, till):
if num % div == 0:
return False
return True
```

In the above algorithm, there is no need to check the divisibility with all numbers less than
$\sqrt{N}$
. According to unique factorization theorem, any number can be represented as a multiplication of prime numbers, so we can modify the above algorithm to check divisibility with only prime numbers less than itself. Additionally, in this way, we are creating *a list of prime numbers* as we go, which is what we wanted all along.

```
# Calculates prime numbers till
class Prime:
def __init__(self, till):
self._till = till
self._primes = []
self._calculate_prime()
def _calculate_prime(self):
def _is_prime(n):
# check if its divisible till sqrt of n if not then its a prime number
check_till = math.floor(math.sqrt(n)) + 1
for p in self._primes:
if p > check_till: return True
if n % p == 0: return False
return True
for n in range(2, self._till + 1):
if _is_prime(n): self._primes.append(n)
def is_prime(self, num):
return num in self._primes
def till(self, num):
for p in self._primes:
if p <= num: yield p
```

Now comes the second part to actually find the largest prime factor. As we know, any number can be represented as a multiplication of primes e.g.
$20$
can be defined as
$2^2 * 5$
. Here we are only interested in the largest prime multiplier (i.e.
$5$
). So we can get to the largest prime multiplier by repetitively dividing all the smaller ones. This way, we optimize the algorithm by choosing a smaller
$N$
instead of a larger one.

```
def largest_prime_factor(n, primes):
check_till = math.floor(math.sqrt(n)) + 1
for p in primes.till(check_till):
while n % p == 0:
n //= p
# p is the last remaining prime number if n is completely divided by it
if n == 1:
return p
# If n in itself is a prime number, it will not be divided by anything
# In that case we return n
return n
```

Final HackerRank submission

```
#!/bin/python3
import sys
import math
class Prime:
def __init__(self, till):
self._till = till
self._primes = []
self._calculate_prime()
def _calculate_prime(self):
def _is_prime(n):
check_till = math.floor(math.sqrt(n)) + 1
for p in self._primes:
if p > check_till: return True
if n % p == 0: return False
return True
for n in range(2, self._till + 1):
if _is_prime(n): self._primes.append(n)
def till(self, num):
for p in self._primes:
if p <= num: yield p
def largest_prime_factor(n, primes):
check_till = math.floor(math.sqrt(n)) + 1
for p in primes.till(check_till):
while n % p == 0: n //= p
if n == 1: return p
return n
primes = Prime(1000001)
t = int(input().strip())
for a0 in range(t):
print(largest_prime_factor(int(input().strip()), primes))
```

Thank you for reading.

## Top comments (1)

Great article, keep the good work! Liked and followed! 🚀