DEV Community 👩‍💻👨‍💻

Cover image for Project Euler #3: Largest prime factor
Kunal Kamble
Kunal Kamble

Posted on

Project Euler #3: Largest prime factor

Links: Project Euler, HackerRank

Problem statement:

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

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 11 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
Enter fullscreen mode Exit fullscreen mode

In the above algorithm, there is no need to check the divisibility with all numbers less than N\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
Enter fullscreen mode Exit fullscreen mode

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. 2020 can be defined as 2252^2 * 5 . Here we are only interested in the largest prime multiplier (i.e. 55 ). 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 NN 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
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode

Thank you for reading.

Top comments (1)

Collapse
 
naubit profile image
Al - Naubit

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

12 Gorgeous UI Components for Your Design Inspiration

>> Check out this classic DEV post <<