Kunal Kamble

Posted on

# Project Euler #3: Largest prime factor

### 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))