Article #7 in a 9-part series.

Like the previous problem, this challenge comes from ProjectEuler.net, “Problem 3”.

Find the largest prime factor of 600,851,475,143.

Now that’s a big number. Test your code with smaller values that you can calculate or look up. “Problem 3” states the largest prime factor of 13,195 is 29, a good test case. Finding primes can take time, so we’ll need to consider our method before tackling 600,851,475,143. There’s some fancy algorithms you could find online, but try it on your own. This makes for a decent software engineer interview question, or just for fun.

Give it a try before looking at my process or solution. Write a function to calculate the largest prime factor of a natural number.

My thinking process

I recalled from school a paper-and-pencil process for finding primes called, the sieve of Eratosthenes. (I didn’t recall the name.) It works by starting with the first prime, 2, and crossing off all multiples of 2. Go to 3, which is prime, and cross off all multiples of 3. 4 is crossed off, so not prime. 5 isn’t crossed off, so is prime. Repeat the process for each natural number until out of paper or time.

Obviously, the sieve of Eratosthenes will take far too long for large numbers, even for a computer due to extensive iteration. Besides, we’re only interested in prime factors, not finding primes. One could use the sieve to find test values, or look up a table of primes.

Since any number can be factored into a product of primes, let’s find factors and divide making the number smaller. I also remembered another handy theorem from my number theory class to help know when to stop looking.

Theorem: if integer n > 1 has no prime divisor <= sqrt(n), then n is prime.

If no factors are found less than the square root of the number, then the number is prime. By finding smaller prime factors and dividing, we would have found any primes larger than sqrt(n) due to product of primes theorem, so we can stop in any case. Start with the smallest prime 2 and test to see if it’s a factor. If so, add 2 to our list of factors and divide the number by the factor. Iterate up as we keep dividing the number into smaller factors until reaching sqrt(n) and we should have our prime factors.

My solution

Here is my solution written in Swift 2 followed by Swift 3. You could try it in a Playground, but keep in mind that using a large parameter will take time. Testing on 13,195 results in 29.

Swift 2: Find Largest Prime Factor
func LargestPrimeFactorOf(value: Int) -> Int

{

    var primeFactorsList: [Int] = []

 
    var num = value

    var factorTest = 2

 
    while num > 1 {

        while num % factorTest == 0 {

            // repeating factors is OK

            primeFactorsList.append(factorTest)

            num = num / factorTest

        }

 
        if factorTest > 2 {

            // test odds;

            // could use primes table, but not much faster

            factorTest = factorTest + 2

        }

        else {

            factorTest = 3

        }

        if factorTest * factorTest > num {

            if num > 1 {

                // Theorem: if integer num > 1 has no prime divisor <= sqrt(num), 

                //   then num is prime.

                primeFactorsList.append(num)

                num = 1

            }

        }

    }

 
    // In Swift, that ! at end reminds reader about unwrapping

    return primeFactorsList.maxElement()!

}

 
LargestPrimeFactorOf(13195)    // 29

//LargestPrimeFactorOf(600851475143)

Swift 3

Swift 3: Find Largest Prime Factor
func LargestPrimeFactorOf(value: Int) -> Int

{

    var primeFactorsList: [Int] = []

 
    var num = value

    var factorTest = 2

 
    while num > 1 {

        while num % factorTest == 0 {

            // repeating factors is OK

            primeFactorsList.append(factorTest)

            num = num / factorTest

        }

 
        if factorTest > 2 {

            // test odds;

            // could use primes table, but not much faster

            factorTest = factorTest + 2

        }

        else {

            factorTest = 3

        }

        if factorTest * factorTest > num {

            if num > 1 {

                // Theorem: if integer n > 1 has no prime divisor <= sqrt(n), 

                //   then n is prime.

                primeFactorsList.append(num)

                num = 1

            }

        }

    }

 
    // In Swift, that ! at end reminds reader about unwrapping

    return primeFactorsList.max()!

}

 
LargestPrimeFactorOf(value: 13195)

In Java:

Java: Find Largest Prime Factor
import java.util.*;

import java.util.Collections;

 
public class PrimeFactors 

{

	public static long largestPrimeFactorOf(long value)

	{

		List<Long> primeFactorsList = new ArrayList<Long>();

 
		long num = value;

		long factorTest = 2l;

 
		while (num > 1) {

			while (num % factorTest == 0) {

				// repeating factors is OK

				primeFactorsList.add(factorTest);

				num = num / factorTest;

			}

 
			if (factorTest > 2) {

				// test odds

				factorTest += 2l;

			}

			else {

				factorTest = 3l;

			}

			if (factorTest * factorTest > num) {

				if (num > 1) {

					// Theorem: if integer n > 1 has no prime divisor <= sqrt(n), 

	                //   then n is prime.

					primeFactorsList.add(num);

					num = 1;

				}

			}

		}		

		return Collections.max(primeFactorsList);

	}

}

Faster algorithms

Searching online reveals Quadratic sieve and Pollard’s Rho algorithm, both described on Wikipedia.

For theorems and proofs, see Elementary Number Theory by Charles Vanden Eynden.

Article #7 in a 9-part series.