Explanation. Standard caveat: don’t look here if you are trying to do these yourself.

The prime factors of 13195 are 5, 7, 13 and 29.It seems so simple at first glance, until of course you look at how big that last number is. I started off by making sure I understood the issue.What is the largest prime factor of the number 600851475143 ?

[code language=“r”]

## check the worked solution

5*7*13*29 # 13195 [/code]

so far so good. At this point I realised that there isn’t an inbuilt `is.prime`

so I stole one from this site.

[code language=“r”] is.prime <- function(num) { if (num == 2L) { TRUE } else if (any(num %% 2L:(num-1L) == 0L)) { FALSE } else { TRUE } } [/code]

Testing the example works pretty well…

[code language=“r”]

## let’s loop up to n and list the prime factors

prime.factors <- function(n) { primes <- c() for(i in 1:n) { ## take advantage of lazy logical evaluation ## and short-cut to only the factors if(n %% i == 0 & is.prime(i)) primes <- c(primes, i) } return(primes) } prime.factors(13195) # 5 7 13 29 [/code]

but I hit a snag when I tried to do the same for the problem value.

[code language=“r”] w <- as.integer(600851475143) ## NAs introduced by coercion prime.factors(600851475143) ## Error: cannot allocate vector of size 4476.7 Gb [/code]

Sure enough, that’s bigger than the machine precision integer allows

[code language=“r”] as.numeric("600851475143") > .Machine$integer.max # TRUE [/code]

so, I abandoned the pre-filled list of values and went again with the brute force. For the sake of speeding it up, I delayed testing for primes until later, as I can do that over the generated list with an `apply`

and only bothered testing the values below `sqrt(n)`

and `n/f`

where `f`

is the largest found prime so far.

[code language=“r”]

## lists are too big. Find the primes by brute force

## using floating point representations

z <- as.numeric("600851475143") i <- 2 factors <- 1

## loop through values of i that are

## less than sqrt(z) and

## less than z/the largest found factor

while(i < sqrt(z) & i < z/max(factors)) { ## skip the prime test for now if(z %% i == 0) factors <- c(factors, i) i <- i + 1 } factors factors.prime <- sapply(factors, is.prime) primes <- factors[factors.prime] # 71 839 1471 6857 z == prod(primes) # TRUE

max(primes) # 6857

### CORRECT

[/code]