Find the largest prime factor of a given number, in this case: 600851475143. A factor of n is a number such that n divided by the factor gives a remainder of zero. A prime factor is a factor which is also a prime number, i.e. it has no factors other than 1 and the number itself.
For example, 12 has the following factors: 1, 2, 3, 4, 6 and 12. The only prime numbers in the factors are 2 and 3, so the highest prime factor is 3.
Solution
A simple brute-force solution to this problem would involve dividing n by every number between 2 and n - 1. If the remainder is zero, then the number is a factor, f, of n and must be checked to see if it is prime. A simple way to do this is to divide f by every number between 2 and f - 1. If none of these divisions result in a remainder of zero then f is prime.
Unfortunately the simple brute-force solution results in:
- n - 2 division operations to find the factors
- f - 2 division operations for each factor to check for primeness
Divisions are an expensive arithmetic operation for CPUs, so we want to minimise them. The highest level at which we can reduce operations is finding the factors of n, because each potential factor p involves 1 division operation (to check if it is a factor) and then up to p - 2 divisions to check for primeness.
One property of factors that is relevant here is that if f is a factor of n, there must be another factor, f’, such that f * f’ = n. This means that if we test all the factors up to n / 2, we will have found all the other factors. This reduces the number of factor checks by 50%.
However, we can do better than checking factors up to n / 2. Since f will always be less than or equal to f’ (assuming we start checking factors from 2 and work upwards), the worst case scenario will be when n is a square number, where f = f’. Therefore, we only need to check factors up to the square root of n, as any factors above sqrt(n) will be paired with a factor below sqrt(n). This will always be less than n - 2 if n > 4.
Once we have our list of factors, we need to find the largest one which is prime. Again we can use the square root shortcut to reduce the number of divisions.
We can also reduce the number of divisions by only attempting to factorise f by prime numbers. This works because every composite (i.e. not prime) number can be expressed as the product of prime numbers, and therefore has at least two prime factors. If a number has no prime factors (other than itself) then it is prime.
Finally, as we are looking for the highest prime factor, we can process the factors in descending order. The first prime factor we come to must be the highest prime factor. This avoids having to check all the prime factors and keep a record of the highest, at the cost of having to sort the factors first (but sorting is generally a cheap operation).
In order to factorise by prime numbers, we need to generate a list of primes. One way to do this is by implementing the Sieve of Eratosthenes, which works as follows:
- Create a list of all numbers up to the target.
- Starting at 2 (the first prime), mark every second number as not prime, as it must be divisible by 2.
- Find the next prime number after 2 and repeat the process, i.e. mark every third number as not prime.
- Continue moving through the grid until you reach the last number.
The major advantage of this algorithm is that it avoids expensive divisions. The only calculation required is to increment the current position by the current prime number, which is a relatively cheap operation on pretty much every processor in existence. The downside is that an array of integers needs to be stored in memory. If we assume an integer is 8 bytes (64 bits), then the total memory required is 8 multiplied by the highest number. In this case, the numbers are small enough to be workable, however we would not be able to use this algorithm if the target was a much larger number.
package main
import (
"fmt"
"math"
"os"
"sort"
)
func getPrimes(maxNumber int) []int {
const UNKNOWN = 0
const NOT_PRIME = 1
const IS_PRIME = 2
const FIRST_PRIME = 2
primes := []int{}
// Use make for the sieve because we know the size and everything should
// be populated with zero
sieve := make([]int, maxNumber+1)
sieve[FIRST_PRIME] = IS_PRIME
for sieveIndex, currentPrime := FIRST_PRIME, FIRST_PRIME; currentPrime != 0 && sieveIndex <= maxNumber; sieveIndex++ {
// Assume this prime will be the last
nextPrime := 0
step := currentPrime
// Mark all multiples of current prime as non-prime
for j := currentPrime + step; j <= maxNumber; j += step {
sieve[j] = NOT_PRIME
}
// Find the next unknown element after the current prime
// This will be the next prime
for k := currentPrime + 1; nextPrime == 0 && k <= maxNumber; k++ {
if sieve[k] == UNKNOWN {
sieve[k] = IS_PRIME
nextPrime = k
}
}
// Set current prime to be the next prime
// If there is no next prime (nextPrime == 0), this will end
// the for loop as currentPrime != 0 will be false
currentPrime = nextPrime
}
// We now have a sieve with all the numbers flagged as prime/not prime
// Extract just the primes and return as a slice
for s := FIRST_PRIME; s <= maxNumber; s++ {
if sieve[s] == IS_PRIME {
primes = append(primes, s)
}
}
return primes
}
func main() {
const TARGET = 600851475143
highestPossibleFactor := int(math.Floor(math.Sqrt(TARGET)))
// Build list of factors from 2 to the highest possible factor
factors := []int{}
for candidateFactor := 2; candidateFactor < highestPossibleFactor; candidateFactor++ {
remainder := TARGET % candidateFactor
if remainder == 0 {
// candidateFactor is a factor, so find its other side
otherFactor := TARGET / candidateFactor
factors = append(factors, candidateFactor, otherFactor)
}
}
// Bail out if we do not have any factors, i.e. TARGET is itself prime
if len(factors) == 0 {
fmt.Println("Target number is prime and therefore has no factors")
os.Exit(1)
}
// Sort factors so we can process them from highest to lowest
sort.Slice(factors, func(a, b int) bool {
return factors[a] > factors[b]
})
// To find whether a factor is prime, we divide it by all the prime numbers
// less than its square root
highestFactor := factors[0]
maxPrimeCandidate := int(math.Floor(math.Sqrt(float64(highestFactor))))
primes := getPrimes(maxPrimeCandidate)
for f := range factors {
// Assume a factor is prime until we factorise it
isPrime := true
for p := 0; isPrime && p < len(primes) && primes[p] < factors[f]; p++ {
remainder := factors[f] % primes[p]
if remainder == 0 {
isPrime = false
}
}
if isPrime {
// This must be the highest prime factor as we process the factors
// in descending order, therefore we can print it and exit
fmt.Println(factors[f])
os.Exit(0)
}
}
// If we get this far, no prime factor was found - i.e. all the factors
// of the target are composite numbers
fmt.Println("Target number has no prime factors")
os.Exit(1)
}