Project Euler #3: Largest prime factor

#projecteuler #math #python #algorithms

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