Largest Prime Factor -

Premise

We are continuing with another Project Euler problem. It asks the following: The prime factors of 13195 are 5, 7, 13, and 29.

What is the largest prime factor of the number 600851475143?

Solution

First, let us cover some theory to make the problem simpler to grasp:

Prime numbers are natural numbers greater than 1 that have no positive divisors other than 1 and themselves. In other words, a prime number is a number greater than 1 that cannot be formed by multiplying two smaller natural numbers.

Prime factors are prime numbers that divide a given integer exactly, without leaving a remainder. Every integer greater than 1 can be expressed as a product of prime numbers, and these prime numbers are its prime factors.

Now we have a couple of different ways to find a solution for a problem like this. The first technique is called trial division (someone might also call it brute force :)).

JavaScript

function largestPrimeFactor(number) {
    factor = 2;
    while (number > 1) {
        if(number % factor === 0) {
            number = number / factor;
        } else if (factor > Math.sqrt(number)) {
            factor = number;
        } else {
            factor++;
        }
    }
    

    return factor;
}

largestPrimeFactor(600851475143);

Python

def largest_prime_factor(number):
    factor = 2
    while number > 1:
        if number % factor == 0:
            number = number // factor
        elif factor > (number ** 0.5):
            factor = number
        else:
            factor += 1

    return factor

result = largest_prime_factor(600851475143)
print(result)

Let us explain our code snippet. We are checking whether the number is divided evenly by our factor. The factor in the initial iteration is 2, which is not divisible by our number, so we increase the factor by 1. The next factor is three, which is also not divisible, and we increase the factor again, all the way until we come to 71, which is our first evenly divisible factor. We divide it by the factor, and the resulting divison is now stored in the number variable. Then we continue, checking for the next factor (if we find it). At one point we’ll have to stop, and the number that is left will be our largest prime factor.

We have two interesting questions to ask here. What is the sqrt doing? Why are we checking against the square root value of our number? Well, we use it to further optimize the algorithm (even though it would still run in O(sqrt(n)) either way). We compare the number against the square root because the largest prime factor of a number could never be bigger than its square root.

A good and simple explanation of this is by looking at a number like 36. The prime factors of 36 come in pairs – for example, 2 and 18, or 4 and 9. If a number has a factor greater than its square root, it obviously should have a pairwise factor smaller than its square root, but we already checked for possible smaller factors than the square root so we already know that we haven’t found such a number.

This could be optimized even further by increasing the number of iterations, we can first check for the factor of two, which is the only even prime number. Then, we know that the number doesn’t have multiples of 2, so we can increase our loop by 2 instead of 1.

Fermat’s factorization method

An alternative way of solving this problem is using Fermat’s factorization method. Fermat’s factorization method is a way to factorize a composite number into its prime factors. It’s based on the idea that every odd composite number can be expressed as the difference between two squares $N=a^2-b^2=(a+b)(a-b)$ .

We would choose a value close to the square root of $N$ . Then we would check if $x^2-N$ is a perfect square, and if it is we have found our and b, and we can further factorize $N$ as $\sqrt{x - (x^{2} - N))}$ and $\sqrt{x + (x^{2} - N))}$ . Then, if any of the factors are prime we would continue the factorization.

For example, if we want to find the largest prime factor of $N=84$ , we can take $x=9$ . $x^2 - N = 81 - 84 = -3$ . Since the result is negative we can’t proceed with Fermat’s factorization for this value, but for $x = 10$ we can. We have $x^2 - N = 100 - 84 = 16$ , which is a perfect square, so now we have $a = 10 + 4 = 14$ and $b = 10 - 4 = 6$ . Neither of those two values are prime so we need to factorize them even further.

Let us implement this in JS and Python:

Javascript

function fermatsFactorization(number) {
    let a = Math.ceil(Math.sqrt(number));
    let counter = 0;
    let primeNumbers = [];
    while((counter + a) < number) {
        let element = Math.pow((a + counter), 2) - number;
        if(Number.isInteger(Math.sqrt(element))) {
            let prime1 = a + counter+Math.sqrt(element)
            let prime2 = a + counter-Math.sqrt(element)
            if(prime2 === 1) {
                primeNumbers.push(prime1)
                break;
            }
            primeNumbers = primeNumbers.concat(fermatsFactorization(prime1))
            primeNumbers = primeNumbers.concat(fermatsFactorization(prime2))
            break;
            
        }
        counter++;
    }

    return primeNumbers;
}

let largestPrimeFactor = fermatsFactorization(600851475143);
console.log(Math.max(...largestPrimeFactor))

Python

import math

def fermats_factorization(number):
    a = math.ceil(math.sqrt(number))
    counter = 0
    prime_numbers = []
    while (counter + a) < number:
        element = math.pow((a + counter), 2) - number
        if math.sqrt(element).is_integer():
            prime1 = a + counter + math.isqrt(element)
            prime2 = a + counter - math.isqrt(element)
            if prime2 == 1:
                prime_numbers.append(prime1)
                break
            prime_numbers.extend(fermats_factorization(prime1))
            prime_numbers.extend(fermats_factorization(prime2))
            break
        counter += 1
    return prime_numbers

largest_prime_factor = fermats_factorization(600851475143)
print(max(largest_prime_factor))

Facebook Tweet Pin LinkedIn