# Prime Factors Problem 2: Largest Prime Factor

Article #**7** in a **9-part** series.

- 1 - Programming Problem: Determine if Two Strings Are Anagrams
- 2 - Programming Problem: Sum-Zero Triplet
- 3 - Programming Problem: Palindromes
- 4 - Problem: Validate a Phone Number
- 5 - Programming Problem: Single-Edit Difference
- 6 - Prime Factors Problem 1: LCM
- 7 - this article
- 8 - How-To: Substrings in Swift
- 9 - Programming Problem: Pangram

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 3

In Java:

### 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.

- 1 - Programming Problem: Determine if Two Strings Are Anagrams
- 2 - Programming Problem: Sum-Zero Triplet
- 3 - Programming Problem: Palindromes
- 4 - Problem: Validate a Phone Number
- 5 - Programming Problem: Single-Edit Difference
- 6 - Prime Factors Problem 1: LCM
- 7 - this article
- 8 - How-To: Substrings in Swift
- 9 - Programming Problem: Pangram