Largest Prime Factors

Problem 3

The prime factors of 13195 are 5, 7, 13, and 29.

What is the largest prime factor of the number 600851475143.

Solution

Let’s solve using Julia

Code

function LargestPrimeFactor(n)
    
    function Factors(n)
        # This function returns all of the factors of n
    
        all_factors = []
            for i = 1:n
                x = gcd(n,i)
                if !(x in all_factors)
                    all_factors = push!(all_factors,x)
                end
            end
            return all_factors
    end

    function IsPrime(n)
        # This function checks whether an integer is is prime

        a = true
        k = 2
        if n == 1
            a = false
        elseif n == 2
            a = false
        end
        
        while k < n
            if n%k == 0
                a = false
                break
            end
            k = k + 1
        end
        return a
    end

    function Primes(x)
        # This function returns a vector of prime numbers of a vector x
        
        x = sort(x)
        primes = []
        for i = 1:length(x)
            if IsPrime(x[i])
                primes = push!(primes, x[i])
            end
        end
        return primes
    end

factors = Factors(n)
primes = Primes(factors)
return primes[end], primes, factors
end

LargestPrimeFactor (generic function with 1 method)

Let’s now test out our code. Let’s first test our code with 10

Code

LargestPrimeFactor(10)

(5, Any[5], Any[1, 2, 5, 10])

Therefore we can see that the factors of 10 are 1, 2, 5, and 10. Of these factors 2 and 5 are prime, and 5 is the largest prime factor.

Let’s now test our code with 37 which is a prime number

Code

LargestPrimeFactor(37)

(37, Any[37], Any[1, 37])

Therefore we have that 37 is the largest prime factor, and all of the factors of 37 are 1 and 37.

Now let’s test our code with 13195

Code

LargestPrimeFactor(13195)

(29, Any[5, 7, 13, 29], Any[1, 5, 7, 13, 29, 35, 65, 91, 145, 203, 377, 455, 1015, 1885, 2639, 13195])

Therefore we get that the largest prime factor of 13195 is 29.

Now let’s find the largest prime factor of 600851475143

Code

LargestPrimeFactor(600851475)

(54499, Any[3, 5, 7, 54499], Any[1, 3, 5, 7, 9, 15, 21, 25, 35, 45  …  13352255, 17167185, 24034059, 28611975, 40056765, 66761275, 85835925, 120170295, 200283825, 600851475])

Therefore we get that the largest prime factor of \(600851475143\) is \(54499\).